Leetcode 137. 只出现一次的数字 II

题目描述

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2] 输出: 3

示例 2:

输入: [0,1,0,1,0,1,99] 输出: 99

解法

因为题目限定了数组中除了一个元素出现一次外，其他元素均出现三次。因为目前并没有三目运算符，所以可以利用现有的逻辑运算，来模拟三进制的不进位加法，对数组中每个元素进行加法运算，最后的结果就是只出现一次的元素。

参考二进制的不进位加法，即异或运算:

xor(1,1)=0
xor(1,0)=1
xor(0,0)=0

三进制的不进位加法中，有一点不同的是，xor(1,1)的结果应该存储起来，再遇到相同位置的1时，即累加到3时，不进位为0。类似于以下效果:

tor(1,1)=2
tor(2,1)=0

其中tor表示为三进制的不进位加法。

因为二进制位只能存储01，所以这里需要借助两个变量来存储一个三进制不进位加法的结果。ones表示二进制加法的结果，twos表示二进制加法的进位。如下所示：

tor(1,1)=(ones=0,twos=1)
tor(1,0)=(ones=1,twos=0)
tor(0,0)=(ones=0,twos=0)

计算规则：观察可以发现，ones的值等同于二进制的xor运算结果，twos用来存储1+1产生的进位，即等同于&与运算的结果。

所以以下代码示例中，使用ones存储二进制加法的结果，twos存储二进制加法的进位。

则对于元素num，根据计算规则，ones^num表示此次的二进制加法结果，不妨以half_ones=ones^num表示该值，若half_ones与twos对应位上的值都为1，则产生进位，如下所示:

h,t=o
1,1=0
1,0=1
0,1=0
0,0=0

左边的h表示half_ones的位，中间的t表示twos的位，右侧的o表示ones的值，ones的值依赖half_ones和twos的情况。观察可发现ones=half_ones&~twos，即ones=ones^num&~twos。

由三进制的不进位加法规则可知，若twos与元素num的对应位上的值都为1，则置twos与ones的对应位为0。ones的值已经经过处理，此处观察twos与num的对应位关系，如下所示:

t,n=h
1,1=0
1,0=1
0,1=0
0,0=0

左边的t表示twos的位，中间的n表示num的位，右侧的h表示half_twos的值，half_twos的值依赖twos和num的情况。观察可发现half_twos=twos&~num，此处的half_twos表示加num后，不进位置0的情况。

根据计算规则，新增的进位为ones&num，更新twos的结果为新增进位和原有进位置0的情况，即twos=(ones&num)|(twos&~num)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones,twos=0,0
        for num in nums:
            ones,twos=ones^num&~twos,ones&num|(twos&~num)
        return ones

参考 Single Number II（模拟三进制法，图表解析）