LeetCode 137. 只出现一次的数字 II
题目描述
题意分析
数组中恰好有一个数出现一次，其他每个不同的数都出现三次，返回那个只出现一次的数值。数组允许零和负数，数值范围覆盖完整的 32 位有符号整数。
要求线性时间和常数额外空间，因此不能靠保存所有频次来求解。这里的重复次数是三次，直接把所有数异或并不能消去重复项。
解法一：逐位计数取模
核心思路
[!blue]
把问题拆成 32 个独立的二进制位。对某一位，出现三次的同一个数要么贡献三个一，要么贡献三个零；所有重复数合起来，该位的一的总数必然是三的倍数。
另外只出现一次的目标数，在这一位只能贡献零或一。因此将该位总计数对三取模，余数就恰好是目标数的这一位。对所有位重复统计，再把余数为一的位置设为一，就能重建整个答案。
负数无需单独取绝对值，因为同一个负数的补码也会完全重复三次，同样满足逐位消去的条件。必须处理第 31 位符号位，否则只能恢复低 31 位，负数会失去符号。
Java 用无符号右移后与一取与，提取指定位置，再直接拼回
int的补码。Go 先转换为uint32，固定只处理低 32 位，重建后转为int32恢复符号，最后再转为返回类型int。
解题步骤
- 初始化答案为零，依次枚举第 0 位到第 31 位。
- 对当前位扫描整个数组，取出每个数在该位的零或一并累加。
- 计数对三取模非零时，把答案对应位置设为一。
- 处理完全部 32 位后，按有符号整数返回重建结果。
代码实现
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int bit = 0; bit < 32; bit++) {
int count = 0;
for (int num : nums) {
count += (num >>> bit) & 1;
}
// 三次重复的位贡献被模三消去，剩下的是单次数在本位的值。
if (count % 3 != 0) {
result |= 1 << bit;
}
}
return result;
}
}
func singleNumber(nums []int) int {
var result uint32
for bit := 0; bit < 32; bit++ {
count := 0
for _, num := range nums {
count += int((uint32(num) >> bit) & 1)
}
// 三次重复的位贡献被模三消去，剩下的是单次数在本位的值。
if count%3 != 0 {
result |= uint32(1) << bit
}
}
// 先恢复三十二位符号，再转换到返回类型。
return int(int32(result))
}
复杂度分析
- 时间复杂度：$O(32n)$，固定扫描 32 个位，每位遍历全部元素。
- 空间复杂度：$O(1)$，只记录当前位计数与结果。
关键点总结
[!green]
- 三次重复按位贡献均为三的倍数，取模后只剩单次数的位。
- 必须包含第三十一位，负数同样通过补码还原。
- Go 的
uint32 → int32 → int转换负责把符号位还原为负值。
解法二：双变量位状态机
核心思路
[!blue]
第一种方法本质上只需要知道每个位的一出现次数对三的余数。可以用两个整数的对应位一起编码这个余数，从而一次位运算就同时更新全部位，无需分别扫描 32 遍。
对任意一位，
(twos, ones)的00表示余数零，01表示余数一，10表示余数二。读到零时状态不变，读到一时按00 → 01 → 10 → 00循环；11不应出现。先算
ones = (ones ^ num) & ~twos。当旧twos为零时，异或让第一次出现的一进入ones、第二次出现的一离开；当旧twos为一时，说明已经累计两次，掩码强制新的ones仍为零，第三次不会重新进入一次状态。再算
twos = (twos ^ num) & ~ones，这里必须读取刚更新的ones。第一次读到一时，新ones为一，会屏蔽twos；第二次时新ones为零，允许twos置一；第三次时异或把原来的twos清零。两式恰好完成所需的三状态循环。两个变量的每一位都独立执行这套更新。所有三次重复的贡献最终归零，目标数为一的位停在
ones中，因此直接返回ones；符号位也遵循同样规则。Go 的&^表示清除右侧为一的位，对应 Java 的& ~。
解题步骤
- 初始化
ones = 0、twos = 0，每个位的计数余数都为零。- 依次读取
num，先用旧ones、旧twos更新ones。- 用旧
twos和已经更新的ones更新twos，不能将两条语句改为同时使用旧值的赋值。- 扫描结束后返回
ones，其中保存了单次出现数的全部二进制位。
代码实现
class Solution {
public int singleNumber(int[] nums) {
int ones = 0;
int twos = 0;
for (int num : nums) {
// 各位并行维护模三状态，第二行必须读取更新后的 ones。
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
return ones;
}
}
func singleNumber(nums []int) int {
ones, twos := 0, 0
for _, num := range nums {
// 各位并行维护模三状态，第二行必须读取更新后的 ones。
ones = (ones ^ num) &^ twos
twos = (twos ^ num) &^ ones
}
return ones
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素只触发常数次位运算。
- 空间复杂度：$O(1)$，只使用两个状态变量。
关键点总结
[!green]
- 状态机是“逐位计数后模 3”的并行写法；
ones、twos分别编码余数 1、2。- 更新顺序属于公式的一部分：先算
ones，再让twos排除新的ones。- 位运算直接作用于补码，符号位与普通位没有区别，因此正负数统一处理。
易错点总结
[!yellow]
- 同时用旧值计算
ones和twos：第一次读入某个为 1 的位后，两者都会置 1，产生不存在的11状态。- 漏掉清除掩码，只写
ones ^= num、twos ^= num：状态不会在第三次出现时归零。- 套用 136 题的单纯异或：一个数字异或三次仍等于自身，无法消掉出现三次的元素。
- 位计数不能漏掉符号位或先取绝对值；Go 直接把无符号结果转成 64 位
int会把负数变成正数，必须先转int32。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 136. 只出现一次的数字 | 简单 | 原题其他值出现两次，可直接异或；本题出现三次，要按位统计模3或用状态机。 |
| 260. 只出现一次的数字 III | 中等 | 同样寻找少数例外值，原题有两个单次值，可按异或差异位分组。 |
| 191. 位1的个数 | 简单 | 按位统计重复模式并重建答案；本题各位计数对三取模，该题统计一个整数的置位数。 |
| 338. 比特位计数 | 简单 | 按位统计重复模式并重建答案；本题各位计数对三取模，该题利用去掉最低置位或右移结果递推计数。 |
| 补充题 115. 其余元素出现 k 次的唯一数 | 简单 | 都逐位统计 1 的出现次数；本题按 3 取模，补充题改为按 k 取模。 |