LeetCode 剑指 Offer 56 - II. 数组中数字出现的次数 II
题目描述
题意分析
整数数组中，恰好一个数只出现一次，其他每种数都出现三次，返回那个唯一的数。重复元素不一定相邻，不能直接利用数组顺序定位。
成对重复可以异或抵消，但相同数异或三次仍会剩下一份。本题应利用“三次”这一条件，在每个二进制位上单独消去重复数的贡献。
解法：逐位计数还原
核心思路
[!blue]
固定一个二进制位。某个出现三次的数，在这一位要么三次都是零，要么三次都是一，因此对该位的一的总数贡献只能是零或三。把所有重复数的贡献相加，结果一定能被三整除。
再加上唯一数的这一位，总计数对三取余后，便只剩唯一数的位值：余数为零表示该位是零，余数为一表示该位是一。不同位之间互不影响，因此逐位还原即可得到整个答案。
对每一位重新将
count清零，扫描所有数，用(num >> bit) & 1取出当前位。若计数模三非零，就用按位或把结果对应位置设为一，其他已经还原的位保持不变。固定扫描 32 位，包含符号位。右移后再与一相与，只读取选定的一位；Java 的
int和 Go 中显式使用的int32都按这 32 位重建结果。若原数为负，最高位也被正常还原，不需要先取绝对值。
解题步骤
- 将结果初始化为零，依次枚举位下标
0到31。- 每一位创建独立计数，扫描全部数组元素，累加该位为一的次数。
- 若
count % 3非零，把结果的当前位设为一。- 所有位处理完后返回还原出的整数；Go 将重建的
int32转换为接口所需的int。
代码实现
class Solution {
// 某一位计数对 3 取余不为 0，说明只出现一次的数字在这一位上是 1。
public int singleNumber(int[] nums) {
int res = 0;
for (int bit = 0; bit < 32; bit++) {
// 每一位独立统计，不能累积上一位的计数。
int count = 0;
for (int num : nums) {
if (((num >> bit) & 1) == 1) {
count++;
}
}
// 三次重复的贡献被消去，剩余就是唯一数的这一位。
if (count % 3 != 0) {
res |= (1 << bit);
}
}
return res;
}
}
func singleNumber(nums []int) int {
// 某一位计数对 3 取余不为 0，说明只出现一次的数字在这一位上是 1。
var res int32
for bit := 0; bit < 32; bit++ {
// 每一位独立统计，不能累积上一位的计数。
count := 0
for _, num := range nums {
if (int32(num)>>bit)&1 == 1 {
count++
}
}
// 三次重复的贡献被消去，剩余就是唯一数的这一位。
if count%3 != 0 {
res |= int32(1) << bit
}
}
return int(res)
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(32n)=O(n)$，整数位宽固定为 32。
- 空间复杂度：$O(1)$，逐位统计，只保存计数与结果，不需要记录每种数的出现次数。
关键点总结
[!green]
- 三次重复对每一位的贡献都是三的倍数，取模只留下唯一数。
- 各位独立统计，设置结果位时用按位或保留其他位。
- 固定 32 位处理能同时还原数值位和符号位。
易错点总结
[!yellow]
- 每进入新的一位都要清空计数，不能累加上一位的统计结果。
- 只做右移还会保留更高位，必须再与
1相与，取出单个位。- 合法输入下余数只可能是零或一，不能等到余数为二才设置结果位。
- 不要对输入先取绝对值，否则会改变原数的二进制表示和最终符号。
- 不能直接异或整个数组，三次重复不会像两次重复那样被抵消。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 136. 只出现一次的数字 | 简单 | 原题其他值出现两次，可直接异或；本题出现三次，要按位统计模3或用状态机。 |
| 260. 只出现一次的数字 III | 中等 | 同样寻找少数例外值，原题有两个单次值，可按异或差异位分组。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！