剑指 Offer 56 - I. 数组中数字出现的次数

问题分析：比较直接的想法，是通过HashMap统计数字出现的次数，或者用一个Set集合遍历数组，如下给出的第一段代码。

上述两种不严格的来说时间复杂度可以达到O（n），但是空间复杂度显然不是O（1），均使用了额外空间。

数组中只出现一次的数字，其他均出现两次，可以联想到异或运算。但是这个只出现一次的数字有两个，换句话说，将数组中的所有数字全部异或之后，所得到的是这两个只出现一次的数字异或的结果，无法分离出这两个数字。

分组，只要能按照某种规则将这两个数字（假设为a,b），分到两组里面，再对两个组全部分别做异或运算，最后便会得到a,b。因为无论按照什么规则分类，出现两次的数字一定会同时被分到一个组里面，因为他们值相同。

分组规则，上述提到过将数组中所有元素进行异或操作，所得到的值为a,b异或的结果，异或本身就表示了两个数字的区别，只有他们不相同的位才会得到1，所以使用所有元素异或结果的最低位作为mask来进行分组。

//Set集合：
class Solution {
    public int[] singleNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
                continue;
            }
            set.add(num);
        }
        int[] ans = new int[2];
        int index = 0;
        for (int num : set) {
            ans[index++] = num;
        }
        return ans;
    }
}

异或操作的代码实现：

//异或操作
class Solution {
    public int[] singleNumbers(int[] nums) {
        int k = 0;
        for (int num : nums) {
            k ^= num;
        }
        
        //int mask = 1;
        //while ((k & mask) == 0) {
        //	mask <<= 1;
        //}
        
        //k & (-k)可以得到最低位的1,等价上面的操作。
        int mask = k & (-k);
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

剑指 Offer 56 - II. 数组中数字出现的次数 II

统计每一位为1的个数，对三取模，过滤掉出现三次的数字，从而得到结果。

class Solution {
    public int singleNumber(int[] nums) {
        //int最多32位，开一个32位的数组统计每个位上1的个数
        int[] count = new int[32];
        //统计每一个数字为1位的情况，对应记录在count[]中
        for (int num : nums) {
            for (int j = 0; j < 32; j++) {
                count[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        //对应高低位，分别模3，出现三次的1位，就会被过滤掉，只留下只出现一次的数
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= count[31 - i] % m;
        }
        return res;
    }
}