题目描述

给你一个整数数组nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

样例

输入：nums = [2,2,3,2]
输出：3

输入：nums = [0,1,0,1,0,1,99]
输出：99

算法1

(哈希表) $O(n)$

时间复杂度： O(n)，其中n是数组的长度。
空间复杂度： O(n)。哈希映射中包含最多n//3+1个元素，即需要的空间为 O(n)。

Python 代码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        freq = collections.Counter(nums)
        for num, occ in freq.items():
            if occ == 1:
                return num

算法2

(位运算) $O(nlogC)$

时间复杂度：我们需要遍历所有的nums数组，这里时间复杂度为O(n)；同时我们要遍历二进制数长度，这里设C为数的大小，所以时间复杂度为O(logC),最终的时间复杂度为O(nlogC)。
空间复杂度： 因为只使用了几个变量，所以空间复杂度为O(1)。

Python 代码

ps. 因为python的整数是无符号的，所以如果在最后需要操作第31位，则表示答案为负数，需要进一步的处理结果。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            total = sum((num >> i) & 1 for num in nums)
            if total % 3:
                # Python 这里对于最高位需要特殊判断
                ans |= (1 << i)
                if i == 31:
                    return ~(ans ^ 0xffffffff)

        return ans