LeetCode 137「Single Number II」详解：位计数 + 模3运算 + 状态机
给定题目是 LeetCode 137「Single Number II」：在一个整数数组中，除了一个元素只出现一次以外，其余每个元素都恰好出现三次，要求在 O(n) 时间、O(1) 额外空间内找出这个只出现一次的元素。cnblogs+1
题意与难点
题目核心约束：
- 所有「杂音」元素都出现 3 次。
- 只有目标元素出现 1 次。
- 不能用哈希表计数（不满足常数空间），也不能排序（不满足线性时间）。leetcode+1
难点在于：如何利用「出现三次」这个信息，把所有重复元素的贡献抵消掉，只保留那个只出现一次的数的 位信息。cnblogs
基础思路：按位计数 + mod 3
可以把每个数当成 32 位二进制整数，从「每一位」的角度来看问题。dbwu+1
对于第 i 位（0 ≤ i < 32）：
- 统计数组里有多少个数在这一位是 1，记为 count[i]。
- 所有出现 3 次的数，如果这一位是 1，就为这一位贡献 3 的倍数个 1。
- 只有那个出现 1 次的数，如果这一位是 1，会多贡献一个 1，使总数变成 3k+1。dbwu+1
因此：
- 对每一位的计数做 count[i] % 3，结果只可能是 0 或 1。
- 结果为 1 的位，说明这一位属于只出现一次的那个数；结果为 0 的位，说明这一位全被「3 次」的元素抵消干净了。linkedin+1
最终，把所有 count[i] % 3 == 1 的位组合起来，就构成答案的二进制表示，从而恢复出这个唯一元素。linkedin+1
这个思路的逻辑完全正确：时间复杂度是 O(32×n) 也就是 O(n)，空间只需要 32 个计数器（常数级），符合题目要求。algo+1
进一步优化：有限状态机（ones / twos）
在按位计数的基础上，可以继续压缩空间，把「每一位出现次数 mod 3」压缩成一个小型有限状态机，用两个整数的比特来并行维护所有位的状态，即常见的 ones / twos 写法。liadbiz.github+1
对于某一位来说，出现次数 mod 3 的状态只有三种：0 次、1 次、2 次。
用两位二进制来编码这三种状态，例如：
- 00：出现 0 次。
- 01：出现 1 次。
- 10：出现 2 次。
- 出现第 3 次时状态回到 00，相当于做了一次模 3 运算。liadbiz.github+1
ones 和 twos 两个整数的每一位就分别代表该位计数的低位和高位，整套逻辑就是在所有位上并行进行一个「模 3 加法器」。csdn+1
最终，出现次数为 1 的那个数的各个位，会停留在状态 01，也就是保存在 ones 里，所以 ones 就是最后答案。csdn+1
这个有限状态机写法本质上是对「按位计数 + mod 3」的进一步压缩与抽象，但核心思想完全一样：利用模 3，把所有出现三次的数字抹掉，只留下出现一次的那个数的位模式。cnblogs+1
负数处理要点
由于题目允许负数，通常使用 32 位有符号整数：
- 在按位计数的方案中，只要一视同仁地处理 32 位（包含最高的符号位），最终重建出来的二进制如果最高位是 1，就对应一个负数，这样也能正确还原结果。vultr+1
- 有些讲解会特别说明第 31 位（符号位）需要单独按补码规则处理，但只要语言本身用补码表示，按位统计 + 重建即可自然兼容。algo+1
小结
- 思想起点：从「数」切换到「位」，对于每一位统计 1 的出现次数。
- 关键观察：出现 3 次的数在每一位上的贡献必然是 3 的倍数，只有目标数让某些位变成 3k+1。
- 实现路径：
- 入门版：32 个计数器 + 双层循环 + mod 3 重构答案。
- 进阶版：用 ones / twos 状态机把每一位的计数 mod 3 压缩到两个整型中。
整道题本质就是一题典型的「按位计数 + 模运算 + 位运算有限状态机」练习，非常适合作为位运算思维的入门模板。dbwu+1