137. 只出现一次的数字 II

思路

这道题我们可以用有限状态自动机（DFA）的思路来做。

之前的只出现一次的数字中，使用异或运算（也就是模2的加法）可以把所有出现两次的数字抵消掉，最后留下只出现一次的数字。

本题我们也可以往这个思路去想，使用模3的加法把出现三次的数字抵消掉（模3的加法也满足交换律和结合律）。

那么如何模拟模3的加法呢？

从模2的加法入手，我们可以把模2加法看成是一个DFA，状态0（即当前位为0）遇到1变为状态1，状态1遇1变为状态0，遇到0都不变。

模3的加法也类似，不过因为要有三种状态，我们需要用两个二进制位来表示。
00 -> 遇到1 -> 01 -> 遇到1 -> 10 -> 遇到1 -> 00。

这样，当我们把所有数字都进行模3加法计算完之后，出现三次的数字全部被抵消掉，状态机退化到只有前两个状态。因此，其第二位就是最终的结果。

最后剩下的问题就是如何模拟这个状态机了。我们可以根据状态机写出真值表，然后通过化简真值表来得到表达式即可。

Code

class Solution {
    public int singleNumber(int[] nums) {
        int a = 0;
        int b = 0;
        for (int i = 0; i < nums.length; i++) {
            int ta = a;
            a = ~a&b&nums[i] | a&~b&~nums[i];
            b = ~ta & (b ^ nums[i]);
        }
        return b;
    }
}