一道有意思的面试算法题
前言
前阵子突发奇想，突然开始刷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
本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！
