用位运算筛选数组中出现次数不一样的数字

题目链接-来源：力扣（LeetCode）

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

思路：

首先，与前一题类似，我们很直观地可以用哈希表记录数字遍历的次数。第二轮遍历的时候判断哈希表对应的键值是否为1即可找到该数字。
如果要将存储空间降到 O(1)，可以采用与位运算类似的思路，不过由于无关数字出现了奇数次，无法使用异或运算抵消的思路，我们需要考虑更一般的解法。
我们仍然将每一个数字视为一个 32 位的二进制数。则对于任意一个出现了 3 次的数字，其每一个位上的数字都出现了 3 次，’0’ 出现 3 次总和还是 ‘0’，而 ‘1’ 出现 3 次后总和为 ‘3’，对 ‘3’ 求余结果均为 0。并且这种结果对所有数字累加后的结果也是成立的，我们只要遍历数组，将每个数字都按二进制位统计该位上 ‘1’ 的个数，最后分别对 ‘3’ 求余，最后拼接成的结果即为「只出现1次的数」的二进制表达。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        for (int num : nums) {
            for (int i = 0; num != 0; num >>>= 1, i++) {
                count[i] += num & 1;
            }
        }
        
        int res = 0;
        
        for (int i = 31; i >= 0; i--) {
            res <<= 1;
            res += count[i] % 3;
        }
        return res;
    }
}