数组 - 只出现一次的数字

题目

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

*****
Written by Zheng Yu on 10 May 2019