LeetCode 137 [Single Number II]

原题

给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。

样例
给出** [1,1,2,3,3,3,2,2,4,1]** ，返回 4

解题思路

• 方法一：三进制不进位加法，比如02 + 01 = 00 (2+1=3做加法不进位)。所以同一个数，比如7的三进制表示为21，21+21+21 = 00 即十进制下的0。最终代码即统计每一位上1，对3取模
• 方法二：分别统计，记录出现一次，两次，三次的数

完整代码

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ones, twos, threes = 0, 0, 0
        for item in A:
            twos |= ones & item      
            ones ^= item          
            threes = ones & twos     

            ones ^= threes         
            twos ^= threes         
        return ones