LeetCode 137 - 只出现一次的数字 II：有限状态机解法

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

算法分析

核心思想：按位计数 mod 3 的有限状态机
技巧要点：用 ones 和 twos 两个寄存器并行追踪所有 bit 的状态
时间复杂度：O(n)
空间复杂度：O(1)

有限状态机原理

基本思路

题目要求找到一个只出现一次、其他都出现三次的元素。对某一 bit（例如第 k 位）来说，三次出现意味着这个 bit 的出现次数对 3 取模，只有一个数的 bit 模式是模 3 结果非 0。

传统做法是对每位做加法计数 mod 3，但那是 O(32) 的循环。当前代码把”每一位 0→1→2→0 的三状态循环”直接改成位运算状态机，从而只需要两个寄存器：

ones：表示该 bit 当前处于”出现 1 次 mod3”
twos：表示该 bit 当前处于”出现 2 次 mod3”

状态机结构

每个 bit 的状态有三种：

S0 = 出现 0 次 mod3（编码：00）
S1 = 出现 1 次 mod3（编码：01）
S2 = 出现 2 次 mod3（编码：10）

这就是一个 2-bit 状态机，状态转移根据当前输入 bit（x 的该位是 0 或 1）进行轮换：

输入=1 时：00→01，01→10，10→00
输入=0 时：保持不变

将所有 bit 平行执行，因此需要 ones 和 twos 两个 32 位寄存器来并行追踪全部状态。

状态转移表

抽象状态机（单 bit）

当前状态	xbit=0	xbit=1
S0	S0	S1
S1	S1	S2
S2	S2	S0

二进制编码状态（单 bit）

使用 (twos, ones) 表示状态，完整真值表如下：

t	o	x	o’	t’	状态变化
0	0	0	0	0	S0→S0
0	0	1	1	0	S0→S1
0	1	0	1	0	S1→S1
0	1	1	0	1	S1→S2
1	0	0	0	1	S2→S2
1	0	1	0	0	S2→S0
1	1	0	0	0	非法状态（不会出现）
1	1	1	0	0	非法状态（不会出现）

可以看到三态循环完全复原：00→01→10→00，对 xbit = 1 时循环，对 xbit = 0 时保持。而 &~ 屏蔽保证永远不进入非法状态 11。

更新公式推导

从真值表到布尔表达式

根据状态转移表，我们可以用卡诺图化简推导出更新公式。

第一步：列出有效状态的真值表

t (twos)	o (ones)	x (输入)	o’ (新ones)	t’ (新twos)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	0	1
1	0	1	0	0

第二步：对 o’ 列卡诺图化简

找出 o’ = 1 的行：第 2 行和第 3 行

        t=0    t=1
ox=00    0      0
ox=01    1      0
ox=11    0      -
ox=10    1      -

化简得：

o' = (o ⊕ x) & ~t

o ⊕ x：当 o 和 x 不同时为 1（覆盖第 2、3 行的 ox 组合）
& ~t：排除 t=1 的情况（非法状态保护）

第三步：对 t’ 列卡诺图化简

找出 t’ = 1 的行：第 4 行和第 5 行

        t=0    t=1
ox=00    0      1
ox=01    0      0
ox=11    1      -
ox=10    0      -

注意：这里用的是**更新后的 o’**，不是原来的 o！

化简得：

t = (~o&~x&t) | (o&x&~t)
↓↓↓
t' = (t ⊕ x) & ~o'

t ⊕ x：当 t 和 x 不同时为 1
& ~o'：排除 o’=1 的情况（因为 o’=1 代表状态 S1，不应该有 twos=1）

第四步：执行顺序的重要性

ones = (ones ^ x) & ~twos;      // 先算 o'
twos = (twos ^ x) & ~ones;      // 再算 t'，用的是新的 ones

关键点：第二行的 ~ones 用的是刚更新完的 ones，不是原来的值！这就是为什么必须先更新 ones，再更新 twos——这是状态机同步的核心机制。

公式含义

ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;

第一行：`ones = (ones ^ x) & ~twos`

ones ^ x：先把该位是否出现一次用 xor 累加（xor 表示”翻转一次”）
& ~twos：强制屏蔽掉那些已经进入状态”出现 2 次”的 bit

第二行：`twos = (twos ^ x) & ~ones`

同理，为出现两次的寄存器做 xor，然后屏蔽掉刚刚更新后的 ones

注意：执行顺序 matters（先 ones，再 twos），因为第二行引用的 ones 已经是更新过的，这正是状态机的核心同步机制。

状态机映射关系

抽象状态机（S0, S1, S2）
        ↕ 映射
二进制位状态 (twos, ones)
        ↕ 真值表
代码里的：
ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones
        ↓
最终答案 = ones（对应 S1 的所有 bit）

为什么 ones 就是答案？

从每一个 bit 位的状态转移可以得出：

回顾状态编码：

S0（出现 0 次）：ones=0, twos=0
S1（出现 1 次）：ones=1, twos=0
S2（出现 2 次）：ones=0, twos=1

关键观察：

出现 3 次的数字：

第 1 次：S0 → S1（ones=1）
第 2 次：S1 → S2（twos=1）
第 3 次：S2 → S0（ones=0, twos=0）

最终状态：S0，ones=0

出现 1 次的数字：

第 1 次：S0 → S1（ones=1）

最终状态：S1，ones=1

因此：

出现 3 次的数字，状态回到 S0，ones=0
出现 1 次的数字，状态停在 S1，ones=1

所以 ones 就是答案！

代码

class Solution {
   public:
    int findNumberAppearingOnce(vector<int> &nums) {
        int ones = 0, twos = 0;
        for (auto x : nums) {
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
            // 上面两行代码等效于下面的代码
            // int o1 = ones;
            // ones = (ones ^ x) & ~twos;
            // twos = (~o1 & ~x & twos) | (o1 & x & ~twos);
        }
        return ones;
    }
};

总结与反思

上面的”位状态机”的思路可以推广到任意 mod-k 的情况。
上面用到的位运算在 cpp 中可以同时处理所有 32 个 bit

TK的小站