题目
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
个人解法
测试用例数(个) | 执行用时(ms) | 战胜 |
---|---|---|
16 | 104 | 70.88% |
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var cache = {};
var len = nums.length;
for (var i = 0 ; i < len ; i++) {
cache[nums[i]] = cache[nums[i]] ? (cache[nums[i]] + 1) : 1;
}
for (var k in cache) {
if (cache[k] === 1) {
return k;
}
}
return 0;
};
最快解法
测试用例数(个) | 执行用时(ms) | 战胜 |
---|---|---|
16 | 56 | 100% |
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
var res;
nums.forEach(function (v) {
res = res ^ v;
});
return res;
};
分析
通过异或巧妙地寻找只出现一次的数字。这里以 [4,1,2,1,2]
为例。
异或运算满足交换律和结合律,即:
(A ^ B) ^ C == C ^ (B ^ A)
所以,我们可以将 [4,1,2,1,2]
进行转换:
4 ^ 1 ^ 2 ^ 1 ^ 2
-->
(1 ^ 1) ^ (2 ^ 2) ^ 4
-->
0000 ^ 0000 ^ 0100
-->
0100
-->
4