一道有意思的面试算法题

maxmin 发布于2019-08-23 14:28 / 2663人阅读

摘要：解决方案异或操作异或运算是对于二进制数字而言的，比如说一个有两个二进制，如果两个值不相同，则异或结果为。比如说，本质上其实是和的每一对比特位执行异或操作，等价于下面数字对应的二进制数字对应的二进制数字对应的二进制因此的结果就为啦。

新年第一篇文章，先祝大家新年快乐！！那么接下来进入正文。

前言

前阵子突发奇想，突然开始刷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和任何一个数字异或呢？结果是数字本身。

我们举个栗子：
假设我们有一个数组，里面元素为[a, a, c, c, b, b, d]。那么我们对数组里的所有元素进行按位异或操作，即a ^ a ^ c ^ c ^ b ^ b ^ d,是不是就等价于0 ^ 0 ^ 0 ^ d = d。而d就是数组里只出现一次的元素。
那么我们可以扩展一下，对于任意满足某个元素只出现一次以外，其余每个元素均出现两次的数组，是不是可以通过这种方式来得到那个只出现一次的元素。

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

/**
 * 只存在一次的数字
 * 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

GPU云服务器云服务器字符串算法面试题面试c语言算法编程题 linux的面试题 js的基础面试题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100669.html

从一道前端面试题谈起

摘要：但是题目非要弄成链表的形式，说实在的，我真没有见过前端什么地方还需要用链表这种结构的除了面试的时候，所以说这种题目对于实际工作是没什么用处的，但是脑筋急转弯的智商题既然这样出了，我们就来看看怎么解决它吧。今天在知乎上看到一个回答《为什么前端工程师那么难招？》，作者提到说有很多前端工程师甚至连单链表翻转都写不出来。说实话，来面试的孩子们本来就紧张，你要冷不丁问一句单链表翻转怎么写，估计...

darkbaby123 2019-08-23 17:53 评论0 收藏0
一道多线程面试题引起的自我救赎

摘要：重温一个面试题内容数组内容为数组内容为个英文字母，使用两个线程分别输入两个数组，打印内容为这样的规律提取一下核心内容，去除次要内容两个线程需要交替执行，打印数字的线程需要先执行，数组打印完毕后线程需要结束。一道多线程面试题引起的自我救赎近日去一个知名互联网企业参加面试，之前准备多多信心满满，但是面试一开始就是一道不起眼的编程题数组A内容为 1,2,3,4...52 ,数组B内容...

BaronZhang 2019-08-14 14:32 评论0 收藏0
前端面试的一道算法题（使用canvas解答）

摘要：据了解，现在前端面试也喜欢考算法题了。下面说一个跟前端有点相关并且有点趣的一道算法题。遍历二维数组连续的个数连续的个数形状的总数第几个形状形状的面积最后的代码图片路径读取整张图片的像素。据了解，现在前端面试也喜欢考算法题了。前几天去面试，果不其然的，面试官给我四道算法题，让我自己回去做。下面说一个跟前端有点相关并且有点趣的一道算法题。题目：平面上有若干个不特定的形状，如下图所示...

hot_pot_Leo 2019-08-21 11:43 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0