一道有意思的面试算法题

时间: 2019-01-05阅读: 1781标签: 算法

前言

前阵子突发奇想,突然开始刷leetcode。其中刷到了一道有意思的题目,发现这道题是当时秋招的时候,腾讯面试官曾经问过我的题目。于是分享给大家看下。


题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。


初步解法

这道题第一眼看过去,思路挺简单的,我们只需要维护一个对象来记录每一个元素出现的次数,使用元素的值作为key,元素出现的次数作为value。之后再遍历这个对象,找到value为1的key。对应的key就是那个元素。代码如下:

function singleNumber(nums) {
  const obj = {};
  for (let i = 0; i < nums.length; i++) {
    obj[nums[i]] = obj[nums[i]] ? obj[nums[i]] + 1 : 1;
  }
  for (let key in obj) {
    if (obj[key] === 1) {
      return Number(key); // 由于 key 是 string ,因此我们这里需要转化下
    }
  }
}

console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8


增加限制

是吧,这道题很简单,那我为什么要说它有意思呢?
因为题目里面其实还有一个限制:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

重点在于不使用额外空间。我们上面那种解法,创建了一个新的对象来储存结果,明显是不行的。那么有没有办法可以只使用原来的数组来实现这个功能呢?


最终解法

我们可以思考下,一个数组里,所有的数字都出现两次,除了一个我们要找的数字只出现一次。那么,我们有没有办法将两个相同的数字给过滤掉呢?

好啦,不卖关子了,之前有了解过的人应该就知道解决方案了,如果之前没了解过这方面东西的人,可以继续往下看。


解决方案:异或操作

异或运算是对于二进制数字而言的,比如说一个有两个二进制a、b,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

JavaScript的按位异或(即^操作)操作,则会对两个数字相应的每一对比特位执行异或操作。

比如说 1 ^ 2,本质上其实是1和2的每一对比特位执行异或操作,等价于下面

  00000000000000000000000000000001 // 数字1对应的二进制
^ 00000000000000000000000000000010 // 数字2对应的二进制
= 00000000000000000000000000000011 // 数字3对应的二进制

因此1^2的结果就为3啦。

那么如果两个相同的数字进行异或操作,结果就可想而知,答案为0啦。

如果是0和任何一个数字异或呢?结果是数字本身。

这样一来的话,我们是不是有了这个问题的解决办法了?我们只需要遍历数组,将所有的值取异或,最终剩下的值,就是那个只出现一次的数字。代码如下:

/**
 * 只存在一次的数字
 * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
 * @param {number[]} nums
 * @return {number}
 */
function singleNumber(nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[0] ^= nums[i];
  }
  return nums[0];
};

console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8]));


结语

这道面试题主要考验面试者对异或的理解,以及能不能活学活用,将这道题与异或联系在一起。当然,最重要的还是多学习、多刷题、多看书。这样才能不断进步。

本文地址在->本人博客地址, 欢迎给个 start 或 follow


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: http://www.fly63.com/article/detial/1773

JavaScript 面试中常见算法问题详解

所谓提升,顾名思义即是 JavaScript 会将所有的声明提升到当前作用域的顶部。这也就意味着我们可以在某个变量声明前就使用该变量,不过虽然 JavaScript 会将声明提升到顶部,但是并不会执行真的初始化过程。

js背包问题算法_JavaScript 背包问题详解

打算好好学一下算法,先拿背包问题入手。最开始的01背包耗时最多,以前只会枚举(就是普通的for循环,暴力地一步步遍历下去),递归与二分,而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

JS数据结构与算法_集合&字典

集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是:集合中的成员是无序的;集合中不允许相同成员存在,计算机中的集合与数学中集合的概念相同,有一些概念我们必须知晓:

js算法实现_二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

JavaScript十大排序必修算法

冒泡排序通过相邻元素的比较和交换,使得每一趟循环都能找到未有序数组的最大值或最小值,双向冒泡普通的冒泡排序在一趟循环中只能找出一个最大值或最小值,双向冒泡则是多一轮循环既找出最大值也找出最小

Js实现插入排序

插入排序是一种非常简单的算法,最适合大部分已经被排好序的数据。在开始之前,通过可视化演示算法如何运作一个好主意。你可以参考前面的动画来了解插入排序的工作原理。

原生js数值开根算法

理论上来讲,开根后的值为x,那么x^2=n,即可以将其转换为数学问题,令y=x^2-n,那么只需要求方程与x轴正方向的焦点就可以得出想要的结果,我们作x=a与方程交于(a^2-n),求得他的切线与x轴的交点

数据结构算法在专网项目中的实践

数据结构与算法作为计算机学科中至关重要的一门课程,在日常业务代码中常常很难用到或者说很难进行相关的实践,我们常常在leetcode中练习的习题感到没有用武之地。实际上,我们可以通过优化页面中的一些代码及在需求实现过程中对之前阅读过的源码或者之前练习过的习题进行相关的举一反三和触类旁通

js实现快速排序算法的2种方式

通过两个for循环,每一次对比相邻两个数据的大小,小的排在前面,如果前面的数据比后面的大就交换这两个数的位置,这个方法就是比较次数太多了,效率比较低。

Js队列和双端队列

最新添加的元素必须排在队列的末尾。在生活中也有队列的应用,比如我们在售票处排队等票,队头的人先拿到票,就走了,而新来的人,就必须排在队伟文明排队。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!