137. 只出现一次的数字 II

题目-中等难度

给你一个整数数组 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 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 位运算

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
         # 初始化32位计数器
        counts = [0] * 32
        
        # 遍历数组中的每个数字
        for num in nums:
            for i in range(32):
                # 统计第i位的1的个数
                counts[i] += (num >> i) & 1
        
        # 还原结果
        res = 0
        for i in range(32):
            # 只保留模3后剩余的位
            res |= (counts[i] % 3) << i
        
        # 处理符号位（第31位为符号位）
        if res >= 2**31:
            res -= 2**32
        
        return res
        

2. 位运算

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            # 更新 ones 和 twos
            # 将当前数字 num 的每一位与 ones 的当前位进行异或操作，并用~two清除那些已经被记录为两次的位
            ones = (ones ^ num) & ~twos
            # 将当前数字 num 的每一位与 twos 的当前位进行异或操作，并用~one清除那些已经被记录为一次的位
            twos = (twos ^ num) & ~ones
        return ones