原题地址：只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
不考虑空间复杂度
不考虑空间复杂度，我们可以利用Set作为辅助，遍历数组时，如果该元素在Set中不存在，则加入进去，如果已经存在，则从Set中删除。对于出现了两次的元素，遍历完成后一定会被从Set中删除，所以最后Set中剩下的就是只出现了一次的元素。
具体的实现代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber1 = function(nums) {
let set = new Set();
for (let i = 0; i < nums.length; i ++) {
if (set.has(nums[i])) {
// set中已经存在则删除
set.delete(nums[i])
} else {
// 不存在则加入
set.add(nums[i])
}
}
// 获取set中唯一的元素
return [...set][0];
};
测试：
let start = new Date();
const test = singleNumber1;
console.log(test([2,2,1])); // 1
console.log(test([4,1,2,1,2])); // 4
console.log(new Date().getTime() - start.getTime()); // 4
时间复杂度： 只需要一次遍历，时间复杂度为$O(N)$
空间复杂度： 需要一个Set作为辅助，最差情况下会存在数组中的一半元素，所以空间复杂度为$O(\frac{1}{2}N)=O(N)$
位运算
题目要求不使用额外的空间，所以上一种方法是不符合题意的。本题需要利用数学的异或运算，它具有如下性质：
- 交换律：a ^ b ^ c = a ^ c ^ b
- 任何数于0异或为任何数 0 ^ n = n
- 相同的数异或为0: n ^ n = 0
利用这三个性质，我们将数组中所有的数进行异或运算，出现了两次的数将被异或为0，最后留下的就是只出现了一次的那个数。
具体的实现代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber2 = function(nums) {
let result = 0;
for (let i = 0; i < nums.length; i ++) {
// 依次异或
result ^= nums[i];
}
return result;
};
测试：
let start = new Date();
const test = singleNumber2;
console.log(test([2,2,1])); // 1
console.log(test([4,1,2,1,2])); // 4
console.log(new Date().getTime() - start.getTime()); // 4
时间复杂度： 一次遍历，时间复杂度为$O(N)$
空间复杂度： 原地处理，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 30,2019