“求只出现一次的数字”系列算法问题

目前遇到的“求只出现一次的数字”系列的算法题目主要有以下三个：

题目一：数组中只有一个元素只出现一次，其余的元素都出现两次，求这个元素；
题目二：数组中只有两个元素只出现一次，其余的元素都出现两次，求这个元素；
题目二：数组中只有一个元素只出现一次，其余的元素都出现三次，求这个元素；

这类算法题目的解决方案主要有以下几种：

方案一：统计每个数字的出现次数

建立一个 Map（key 为数组中的元素，value 为该元素出现的次数），遍历数组中的所有元素，最后再遍历 Map 找到只出现一次的元素。

function singleNumber(nums = []) {
    let map = {};
    nums.forEach(num => map[num] ? map[num]++ : (map[num] = 1));
    return Object.keys(map).filter(num => map[num] === 1).map(num => parseInt(num));
}

该方法优点是比较简单，可以解决上面三个题目，但是空间复杂度比较高，如果数组元素比较多时，map 占用空间太大。

方案二：统计每个二进制位出现次数

因为题目中的数字是 Int 类型，可以建立一个大小为 32 的数组，来统计每一位上 1 出现的个数，如果某一位上为 1 的话，那么如果该整数出现了三次或者两次（看题目中其余元素出现的次数），对 3 或者 2（具体看题目中）取余为 0，这样把每个数的对应位都加起来对 3 或者 2 取余，最终剩下来的那个数就是单独的数字：

function singleNumber(nums = []) {
    let res = 0;
    for (let i = 0; i < 32; i++) {
        let sum = 0;
        for (let j = 0; j < nums.length; j++) {
            sum += (nums[j] >> i) & 1;
        }
        res |= (sum % 2) << i;
    }
    return res;
}

这个对于大数据量的情况下，相对于方案一，空间复杂度要小很多，但是这个方案只能解决题目一和题目三的问题，对于题目二中，有两个元素只出现一次却无能为力。

方案三：位运算的灵活应用

《题目一》位运算解决方案：

想到位运算中的异或操作可以使两个相同的数字进行异或操作结果必为 0，那么我们可以遍历整个数组，对所有元素进行异或操作，所有出现两次的元素异或结果都变成 0 了，那么剩下的肯定就是那个只出现一次的数字了，是不是很神奇：

function singleNumber(nums = []) {
    let res = 0;
    nums.forEach(num => res = res ^ num);
    return res;
}

这个解法代码量少，时间复杂度和空间复杂度都最低。

《题目二》位运算解决方案：

如果只有一个数字出现一次，我们可以通过异或的方式直接得到该数字，如果两个数字只出现一次的情况下，得到的异或的结果必然是这两个数字的异或的结果，那么我们如何拆分呢？我们可以想到，如果这个结果某个位等于 1（随便找一个为 1 的位即可），那么必然是这两个数字里对应的二进制位一个是 0，一个是 1，那么我们就可以根据该位把列表里所有的数字分为两类，一类是该位是 0 的列表，一类是该位是 1 的列表，那么《题目二》就被拆解成《题目一》的两个子问题，同样可以获取到这两个只出现一次的数字：

function singleNumber(nums = []) {
    let res = 0;
    nums.forEach(num => res = res ^ num);
    let i = 0;
    while(!((res >> i) & 1)){
        i++;
    }
    let res1 = 0, res2 = 0;
    nums.forEach(num => {
        if((num >> i) & 1){
            res1 = res1 ^ num;
        }else{
            res2 = res2 ^ num;
        }
    });
    return [res1, res2];
}

《题目三》位运算解决方案：

对于《题目三》，如果我们直接使用方案一和方案的方式去解决问题，好像并不管用，因为其余元素出现的次数是三次，异或并不能使其余元素结果变为 0，如果异或操作的三进制，那么或许可以，可惜异或目前只能操作二进制，那么有没有一种方案可以模拟三进制操作呢，答案是肯定的。

我们可以用 3 个整数来表示各位出现 1 的次数情况：

ones 表示每个位只出现了 1 次 1 的情况
twos 表示每个位只出现了 2 次 1 的情况
threes 表示每个位只出现 3 次 1 的情况

function singleNumber(nums) {
    let one = 0, two = 0, three = 0;
    for (let i = 0; i < nums.length; i++) {
        //如果最近连续两次为 1，或者原先 two 就为 1，那么 two 就为 1，two 的计算必须放在 one 前面，这里的 & 是与上一次的 one 
        two |= one & nums[i];  
        //每次通过异或更新只出现的一次的结果，和《题目一》《题目二》的类似
        one ^= nums[i];
        //如果一个位既出现了一次，也出现了两次，表示这个数字出现了3次
        three = one & two;
        //清零 one，two 中出现三次的位
        one &= ~three;
        two &= ~three;
    }
    return one;
}