用-按位统计-找唯一出现少于-3-次的数

在这里插入图片描述这道题如果用哈希表统计次数，空间复杂度是 O (n)；

如果用异或，只能处理 “出现偶数次抵消” 的情况（比如出现 2 次），面对 3 次、5 次这类奇数次数就失效了。

首先，这里用到了一个核心规律：

对于任意一个二进制位（比如第 0 位、第 1 位），如果某个数出现了 m 次，那么这个数在该位上的 1 的总贡献，一定是 m 的倍数。

代码逻辑

1. 按位统计 1 的个数

1
2
3
4
5
6


int[] cnts = new int[32]; 
for (int num : arr) {
    for (int i = 0; i < 32; i++) {
        cnts[i] += (num >> i) & 1; 
    }
}

2. 重构目标数

1
2
3
4
5
6


int ans = 0;
for (int i = 0; i < 32; i++) {
    if (cnts[i] % m != 0) {
        ans |= (1 << i); 
    }
}

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


// LeetCode 137（其他数出现3次，目标数出现1次）
public static int singleNumber(int[] nums) {
    return find(nums, 3); // 直接调用通用解法，m=3
}

// 通用解法：数组中只有1种数出现次数<m，其他数都出现m次，返回该数
public static int find(int[] arr, int m) {
    // cnts[i]：统计数组中所有数在第i位（0~31）上1的总个数
    int[] cnts = new int[32]; 
    
    // 遍历数组，统计每一位上1的总个数
    for (int num : arr) {
        for (int i = 0; i < 32; i++) {
            // 提取num第i位的1，累加到cnts[i]
            cnts[i] += (num >> i) & 1; 
        }
    }
    
    // 根据cnts重构目标数
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        // 如果第i位1的总个数不是m的倍数，说明目标数第i位是1
        if (cnts[i] % m != 0) {
            // 把第i位设为1
            ans |= (1 << i); 
        }
    }
    
    return ans;
}