题目分析

这个题目比昨天的题目难度大很多，是谷歌公司面试的一道题目，拍了拍自己的胸脯，幸好没去谷歌（狗头保命）。

位运算

想一下每个元素出现两次时是咋做的？是不是记录二进制位中1出现的个数，并对2求余。一个数如果某一位是1，出现2次，就为2，然后对2求余就为0。因此单独的一个数对2求余就为1，所以该数在哪些位置上为1，则最后的结果在哪些位置上也为1。设当前某一位为0，下一个数在该位上为1，那么该位的状态位1，下一个数在该为上位0，那么该位的状态位0。设当前某一位为1，下一个数在该位上为1，那么该位的状态位0，下一个数在该为上位0，那么该位的状态位1。这不正好符合异或的定义吗？

那我们考虑一下每个元素出现三次时的情况，也应该记录二进制位中1出现的个数，并对3求余，一个数如果某一位是1，出现3次，就为3，然后对3求余就为0。因此单独的一个数对3求余就为1，所以该数在哪些位置上为1，则最后的结果在哪些位置上也为1。但是出现了一个问题，出现2次，余数可以用0和1表示，那么出现3次如何表示呢？余数为0，1，2，需要使用3个状态表示，也就是需要两位表示。

下面借用Leetcode Krahets(K神)的图

当two为0时，如果下一个数为0，则one的状态不变，如果下一个数为1，则one的状态反转。
当two为1时，无论下一个数时0还是1，one都为0。
可以列出下表进行推导one为0或者1时，two的变化，注意one为更新后的值。

class Solution:
    def singleNumber(self, nums):
        ones, twos = 0, 0
        for num in nums:
            ones = ones ^ num & ~twos
            twos = twos ^ num & ~ones
        return ones

刷题总结

大佬的思路太漂亮，不禁感叹自己还是太菜啦~，我们不是要记住这一题，而是要记住状态转移的方式，然后列表推导出下一个状态的表达式，这个才是这个问题的核心，以后无论数据重复多少次都有类似的解法。