137. 只出现一次的数字 II

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 3 * 10^4
  -2^31 <= nums[i] <= 2^31 – 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

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

Python 解答：
1.暴力

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        adic = {}
        for item in nums:
            if item not in adic.keys():
                adic[item] = 1
            else:
                adic[item] += 1
        for key in adic.keys():
            if adic[key] == 1:
                return key

时间复杂度：O(n)
空间复杂度：O(n)

2.位运算

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        LENS = 32
        mask = 1
        total = 0
        for _ in range(LENS):
            r = 0
            for num in nums:
                r += num & mask
            if r%3:
                total += mask
            mask <<= 1
        if total > 2**31-1:
            total = ~(total^0xffffffff)
        return total

3.位运算优化

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        LENS = 32
        mask = 1
        ans = 0
        for i in range(LENS):
            r = 0
            for num in nums:
                r += num & mask
            if r%3:
                if i != 31:
                    ans |= mask
                else:
                    ans -= 2**31
            mask <<= 1
        return ans