jz056II.数组中数字出现的次数II

题目链接

如果我们把题目改成数组中的数字除某一个外只出现一次，其他数字出现了两次，那么我们就能用异或很方便地解决。但是在现在这种情况下，由于三个相同的数字的异或结果还是该数字，这种方法不能直接使用。尽管如此，我们还是可以沿用位运算的思路。如果一个数字出现三次，那么他的二进制位表示的每一位（0或1）也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除。因此我们可以把数组中所有数字的二进制表示的每一位都加起来，如果某一位的和能被3整除，那么那个只出现一次的数字二进制表示中对应的那一位是0，否则是1。该算法的实现如下所示。输出前要先判断结果是正数还是负数，如果为正数那么第32位是0，如果是负数那么第32位是1。要注意的是，由于在python中负数存储的特殊性，我们要先将0-32位取反（即res ^ 0xffffffff）然后将所有位数取反。这个算法的时间复杂度是O（N），空间复杂度是O（1）。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = [0] * 32
        for num in nums:
            for j in range(32):
                counts[j] += num & 1
                num >>= 1
        res, m = 0, 3
        for i in range(31, -1, -1):
            res <<= 1
            res |= counts[i] % m
        return res if counts[31] % m == 0 else -(res ^ 0xffffffff)