137-single-number-ii.md

137. 只出现一次的数字 II - medium

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

 

示例 1：

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

示例 2：

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

 

提示：

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

 

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

Solutions

1. 排序遍历

先排序，然后每步 3 个做遍历

时间复杂度取决于排序取 O(n * log n), 空间复杂度 O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()

        n = len(nums)
        i = 0
        while i + 2 < n:
            if nums[i] != nums[i + 1]:
                return nums[i]
            i += 3
        
        return nums[-1]

2. hash map

通过 map 统计数据个数，出现次数为 3 则丢弃，最终只剩下出现次数为 1 的值

时间复杂度为 O(n), 空间复杂度 O(n)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        m = {}
        for n in nums:
            c = m.pop(n, 0)
            c += 1
            if c == 3:
                continue
            m[n] = c

        i, _ = m.popitem()
        return i

3. 二进制位运算

参考题解，有一个思路是，确定每一个二进制位。

对 nums 中所有第 i 个二进制位求和 total，如果 total % 3 == 0 说明答案值在 i 位为 0，否则为 1。i 取 [0, 31]

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            total = sum((v >> i & 1) for v in nums)
            if total % 3 == 0:
                continue
            if i == 31:
                # 最高位为 1，表示这是个负数。负数存储的是补码（原码取反 + 1）。
                # 等于 `ans - 1 << 32`
                ans -= (1 << i)
            else:
                ans |= (1 << i)
    
        return ans