137 只出现一次的数字 II

标签: 位运算

题目

题目链接：137 只出现一次的数字 II

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

说明：

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

示例 1:

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

示例 2:

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

思路

1. 由于一定有一个「只出现了一次的数字」，因此，可以统计每位上为 1 的个数。用 1 的个数对 3 取模，可以析出「只出现了一次的数字」在该位上的数字。

2. 如：输入 [2,2,3,2]

    2: 010
    2: 010
    3: 011
    2: 010
    -------
       041   (1 的个数统计)
       011   (对 3 取模)
         3   (转换为整型)
   

3. 参考 Lucifer 的题解：

   • 为什么Python最后需要对返回值进行判断？

   如果不这么做的话测试用例是[-2,-2,1,1,-3,1,-3,-3,-4,-2] 的时候，就会输出 4294967292。 其原因在于Python是动态类型语言，在这种情况下其会将符号位置的1看成了值，而不是当作符号“负数”。 这是不对的。 正确答案应该是 - 4，-4的二进制码是 1111…100，就变成 2^32-4=4294967292，解决办法就是 减去 2 ** 32 。

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        '''
        统计每个位为 1 的个数，再看是否为 3 的倍数。
        如果不为 3 的倍数，说明「只出现一次的数字」在该位上为 1
        '''
        res = 0
        for i in range(32):
            # 从低位开始
            bit = 1 << i
            # 统计该位为 1 的个数
            count = 0               
            
            for n in nums:
                # n 在 bit 位为 1
                if n & bit != 0:    
                    count += 1
            # 看看是否为 3 的倍数
            if count % 3 != 0:      
                res |= bit

        # 如果 res > 2 ** 32 - 1，那么就为负数，且首位为符号位，而不是数值。
        # 要求得原来得负数，就减去 2 ** 32
        return res - 2 ** 32 if res > 2 ** 31 - 1 else res