leetcode题解137：只出现一次的数字 II

描述

分析

这题本身难度并不高，只不过是一种巧妙的解法难以想到。题目要求空间复杂度为常数级，所以哈希表的解法（不合题意）就不介绍了。

先介绍一个简单的解法，位运算。由于其它数字都出现三次，很容易想到mod 3运算，将所有数字变为32位二进制，对于所有数字上的第i位上的二进制位求和，然后mod 3就是最终结果的二进制表示的第i位，这种解法非常简单且容易理解。

上面的解法需要对32位进行遍历，求出每一位上的二进制结果。其实有一种一次同时求出32位上的二进制结果的方法，就是用有限状态机。我们首先看下某一位上的计算过程，已计算的结果用x表示，新来的数位用y表示，那么计算公式为
\[ x = (x + y) \mod 3 \]

状态变化过程：
| x | y | 新x |
| :-: | :-: | :-: |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 2 |
| 2 | 0 | 2 |
| 2 | 1 | 0 |

由于x的取值为0,1,2，所以为了使用位运算计算将x拆分为两位，分别计算两位的状态，合起来就是最终结果，用(a,b)来表示x的高位和低位。状态变化更新为：

状态变化过程：
| (a,b) | y | 新(a,b) |
| :-: | :-: | :-: |
| (0,0) | 0 | (0,0) |
| (0,0) | 1 | (0,1) |
| (0,1) | 0 | (0,1) |
| (0,1) | 1 | (1,0) |
| (1,0) | 0 | (1,0) |
| (1,0) | 1 | (0,0) |

其实上面就是真值表（假定都学过数字电路），可以推出计算公式为
\[ a_1 = \bar aby + a \bar b \bar y \\ b_1 = \bar a \bar b y + \bar a b \bar y \\ a = a_1 \\ b = b_1 \]
不化简也可以。每次来一个y计算出新的(a,b)；会发现对于32位中的每一位同时按照这种方式计算，相当对上述运算开启并行度32，得到的结果就是每一位上的二进制结果。

这样写的代码其实已经是符合题意的了，但是公式可以继续简化，比如
\[ b = \bar a \bar b y + \bar a b \bar y = \bar a (b \oplus y) \]
还可以继续，比如我们先计算出b_1，然后根据(a, b_1)计算出a_1，一样的先画真值表，然后推出公式：
\[ b_1 = \bar a (b \oplus y) \\ a_1 = \bar b_1 (a \oplus y) \\ a = a_1 \\ b = b_1 \]
由于(a1,b1)不是同时求出来的，所以写代码的时候可以简化
\[ b = \bar a (b \oplus y) \\ a = \bar b (a \oplus y) \]

我们再来看看最终结果是什么，由于只有一个没有出现三次，所以最终结果只能是(0,0)=0,(0,1)=1，不可能出现(1,0)=2的情况，所以最终结果直接取b的值即可。

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a, b = 0, 0
        for x in nums:
            b = ~a & (b ^ x)
            a = ~b & (a ^ x)
        return b