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

最容易想到的自然还是map计数

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(var num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for(var num : map.keySet()) {
            if(map.get(num) == 1) {
                return num;
            }
        }
        return 0;
    }
}

时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)，其中时间复杂度可能要超过\(O(n)\)，其中包括哈希表的扩容操作。
这里的运用位运算的方法我属实是想不太来，这里用了一个32位的数组来计算每一个二进制位出现的次数，如果一个数字出现了3次，那么它的每一位肯定也是出现了3次的，所以我们枚举每一个数字，将每个数字的二进制位出现的次数更新，再遍历\(map\)数组，如果\(map[i]\)出现的次数不是3的倍数，那么这一位肯定就是单独的那个数字中的，我们将每一位的位权相加即可。

class Solution {
    public int singleNumber(int[] nums) {
        int[] map = new int[32];
        for(var num : nums) {
            for(int i = 0; i < 32; i++) {
                map[i] += (num & 1);
                num >>= 1;
            }
        }
        int res = 0;
        for(int i = 31; i >= 0; i--) {
            res = res << 1;
            if(map[i] % 3 == 1) {
                res |= 1;
            }
        }
        return res;
    }
}