LeetCode 137. 只出现一次的数字 II
目录
题目描述
题意分析
一个整数数组里，只有一个元素恰好出现一次，其余每个元素都恰好出现三次，要求把这个唯一元素找出来。
约束里有两个明显的信号。一是题目额外要求线性时间复杂度并且只用常数额外空间，这等于直接封死了「开一张表记录每个数出现几次」的路子——那条路一定对，但空间是 $O(n)$。二是元素范围是 32 位有符号整数，也就是说唯一元素本身完全可能是负数，任何默认「答案是正数」的处理都会翻车。
还要看清一点：出现三次的元素之间可以任意穿插，题目没有保证它们相邻，也没有保证数组有序，所以答案不能依赖任何位置关系。
边界主要有三处：数组长度可能只有 1，此时唯一元素就是它自己；唯一元素可能是负数，符号位不能漏；出现三次的元素本身也可能是负数，统计时不能对它们做绝对值处理。
解法：双变量位状态机
核心思路
对每个二进制位单独看，只需记录该位出现 1 的次数对 3 的余数。余数只有 0、1、2 三种状态，可用
twos和ones的对应位编码为00、01、10。当前数某位为 0 时状态不变；为 1 时状态按
00 → 01 → 10 → 00循环。位运算可以让所有二进制位并行完成这套状态转移：ones = (ones ^ num) & ~twos twos = (twos ^ num) & ~ones
ones必须先更新，第二行使用新的ones，从而保证同一位不会同时出现在两个状态变量中。遍历结束时，出现三次的数字在每一位都回到00；唯一数字贡献的位停在01，所以ones就是答案。补码的符号位也参与相同转移，负数无需特判。
解题步骤
- 初始化
ones = 0、twos = 0，所有位的计数余数均为 0。- 依次读入每个
num，先更新ones，再用更新后的ones更新twos。- 遍历结束返回
ones。以
[2, 2, 3, 2]的第 1 位为例，该位依次读到1、1、1、1，状态依次为01、10、00、01，最终余数为 1；第 0 位只有数字 3 贡献一次 1，也停在01，两位合起来得到 3。
代码实现
class Solution {
public int singleNumber(int[] nums) {
int ones = 0;
int twos = 0;
for (int num : nums) {
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 ^ num) &^ twos
twos = (twos ^ num) &^ ones
}
return ones
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素只触发常数次位运算。
- 空间复杂度：$O(1)$，只使用两个状态变量。
关键点总结
- 状态机是“逐位计数后模 3”的并行写法；
ones、twos分别编码余数 1、2。- 更新顺序属于公式的一部分：先算
ones，再让twos排除新的ones。- 位运算直接作用于补码，符号位与普通位没有区别，因此正负数统一处理。
- 若面试官追问“其余数字出现 k 次”，逐位统计 32 位并对 k 取模更容易推广；双变量状态机只针对模 3 做了压缩。
易错点总结
- 同时用旧值计算
ones和twos：第一次读入某个为 1 的位后，两者都会置 1，产生不存在的11状态。- 漏掉清除掩码，只写
ones ^= num、twos ^= num：状态不会在第三次出现时归零。- 套用 136 题的单纯异或：一个数字异或三次仍等于自身，无法消掉出现三次的元素。
- 对负数先取绝对值：会破坏符号位，
[-2, -2, -2, -3]会错误地返回 3。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 136. 只出现一次的数字 | 简单 | 异或自反性 |
| 260. 只出现一次的数字 III | 中等 | 最低位分组 |
| LCR 004. 只出现一次的数字 II | 中等 | 逐位模 3 计数 |
| 剑指 Offer 56 - I. 数组中数字出现的次数 | 中等 | 分组异或 |
| 剑指 Offer 56 - II. 数组中数字出现的次数 II | 中等 | 双变量状态机 |