只出现一次的数字 II：其余出现三次怎么办？（LeetCode 137）

简化版

数组里除了一个元素只出现一次，其余都恰好出现三次，找出那个单独的。因为「三次」用异或消不掉，改用按位统计：对二进制的每一位（共 32 位），统计所有数字在该位上 1 的总个数，如果某位的 1 的总数不能被 3 整除，说明那个只出现一次的数在这一位上是 1。把这些位拼起来就是答案。也可用「位运算状态机」用两个变量模拟「模 3 计数」。

详细版

解法一：按位统计（直观，O(32n)）

int singleNumber(int[] nums) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        int count = 0;
        for (int n : nums) {
            count += (n >> i) & 1;     // 统计第 i 位上 1 的个数
        }
        if (count % 3 != 0) {          // 不能被 3 整除 → 单独的数这位是 1
            res |= (1 << i);
        }
    }
    return res;
}

解法二：位运算状态机（O(n)，进阶）

int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int n : nums) {
        ones = (ones ^ n) & ~twos;     // 出现 1 次的位
        twos = (twos ^ n) & ~ones;     // 出现 2 次的位
    }
    return ones;                        // 出现 3 次的位被清零，剩 1 次的
}

核心思想：出现三次的数，在每一位上贡献的 1 的个数是 3 的倍数；单独的数打破了这个「模 3 为 0」。
按位统计法通用（改成模 k 可解「其余出现 k 次」）；状态机法更快但难记。
复杂度：解法一 O(32n)、解法二 O(n)，都 O(1) 空间。

完整版教学

一、为什么异或在这里失效

136 题（其余出现两次）用异或，因为 x^x=0——偶数次的都能两两抵消。但这里其余出现三次（奇数次），三个相同的数异或 x^x^x = x，不但消不掉，还留下一个 x 混进结果。所以异或整体套路失效，需要换思路。

二、解法一：按位统计「模 3」

换个角度想：逐位考察。对二进制的第 i 位，把所有数字在这一位上的值（0 或 1）加起来：

出现三次的数字，若它第 i 位是 1，就贡献 3 个 1（是 3 的倍数）；若是 0，贡献 0。
唯一出现一次的数字，若它第 i 位是 1，就额外贡献 1 个 1。

所以第 i 位所有 1 的总数 mod 3：如果结果是 0，说明单独的数这一位是 0；如果是 1，说明单独的数这一位是 1。逐位算出答案的每一位，res |= (1 << i) 拼起来。

这个方法通用性极强：把 % 3 改成 % k，就能解「其余出现 k 次、找一个出现一次」的任意变体。面试首推它，好理解好推广。

注意负数：第 31 位是符号位，用 (n >> i) & 1 逐位取即可，最后拼出的 res 若第 31 位是 1，在 Java 里自然就是负数补码，无需特殊处理。

三、解法二：位运算状态机（进阶，O(n) 一次遍历）

按位统计要遍历 32 位 × n 个数。更快的是用两个变量 ones、twos 模拟每一位的「模 3 计数器」：

每一位的出现次数在 0 → 1 → 2 → 0 之间循环（模 3）。
用两个 bit（ones 的对应位、twos 的对应位）编码这三种状态：(twos,ones) = (0,0) 出现 0 次、(0,1) 出现 1 次、(1,0) 出现 2 次，第三次回到 (0,0)。
转移公式：ones = (ones ^ n) & ~twos；twos = (twos ^ n) & ~ones。遍历完，出现三次的位都归零，ones 里剩下的正是只出现一次的数。

这个解法快但极难现场推导，建议记结论，面试若被追问 O(n) 再抛出。理解上把它当「每个 bit 独立跑一个模 3 自动机」即可。

四、两种解法怎么选

	按位统计	状态机
时间	O(32n)	O(n)
空间	O(1)	O(1)
好懂	✅ 很直观	❌ 难推导
可推广	✅ 改模数即可	需重新设计状态

面试策略：先讲按位统计（稳、能推广到出现 k 次），提一句「还有 O(n) 的位运算状态机 ones/twos」展示深度。

五、易错点

误用异或：出现三次不能异或消除，这是最大陷阱。
循环 32 位而非 64：int 是 32 位。若是 long 要 64 位。
模 3 判断写成 == 1：应写 % 3 != 0（虽然这里非 0 只能是 1，但语义上是「不被 3 整除」）。
状态机公式顺序：先算 ones 再算 twos（twos 用到刚更新的 ones），顺序反了就错。

六、按位模 3 与状态机是同一个计数问题

对每个二进制位独立看，普通元素在该位贡献的 1 总数是 3 的倍数，模 3 后只剩答案位。ones/twos 状态机则把 32 个独立的模 3 计数器并行装进两个整数：状态按 00→01→10→00 循环。二者原理相同，只是表达层次不同。

示例 [2,2,3,2]，低两位：2=10，3=11
第 0 位的 1 总数：0+0+1+0 = 1，1 mod 3 = 1
第 1 位的 1 总数：1+1+1+1 = 4，4 mod 3 = 1
其余位总数为 0
重建结果低两位为 11₂
答案 3

校验维度	本题必须保持的结论
循环/递推不变量	按位统计法保持每个位的计数；状态机保持 ones 表示计数模 3 为 1、twos 表示模 3 为 2。
边界条件	要扫描 32 位才能保留负数的符号位；不能只扫描到数值看似为 0。
复杂度与代价	按位法 O(32n)，状态机 O(n)；固定字宽下都为 O(n) 时间、O(1) 空间。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：按位统计法保持每个位的计数；状态机保持 ones 表示计数模 3 为 1、twos 表示模 3 为 2。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“示例 [2,2,3,2]，低两位：2=10，3=11”开始手推，最后应得到“答案 3”。
边界复核：要扫描 32 位才能保留负数的符号位；不能只扫描到数值看似为 0。
代价复核：按位法 O(32n)，状态机 O(n)；固定字宽下都为 O(n) 时间、O(1) 空间。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“按位统计法保持每个位的计数；状态机保持 ones 表示计数模 3 为 1、twos 表示模 3 为 2。”这条正确性主线不能省。

八、常见误区与追问

误区：全体异或仍能消掉出现三次的元素。 x^x^x=x，三次不会归零，因此普通异或失效。
误区：按位计数只适用于非负数。 扫描完整 32 位并按补码重建时，负数符号位也能正确恢复。
误区：ones 和 twos 是两个真实集合。 它们是 32 个并行模 3 计数器的位平面，不存放具体元素。
追问：若普通元素出现 k 次怎么办？ 通用做法是每位计数后 %k；有限状态机也可设计但表达更复杂。
追问：状态更新顺序为何重要？ 新 twos 会依赖更新后的 ones 或特定公式，随意交换语句会破坏状态转移。
追问：面试优先写哪种解法？ 先写按位模 3，证明直观且不易错；状态机适合作为进一步优化。

九、加强记忆

只出现一次的数字 II（其余出现三次）= 按位统计模 3。异或对「三次」失效，改逐位统计：第 i 位所有 1 的总数 % 3，非 0 则单独的数这位是 1，res |= (1<<i) 拼出答案，O(32n) O(1)，且改模数可解「出现 k 次」的通用变体。进阶用 ones/twos 位运算状态机（每个 bit 跑模 3 自动机）达 O(n)，公式 ones=(ones^n)&~twos; twos=(twos^n)&~ones，返回 ones。核心：三次消不掉就按位数 1、模 3。

简化版

详细版