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