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中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
法 1 异或
思路
将每个数想象成32位的二进制，对于每一位的二进制的 1 和 0 累加起来必然是 3N 或者 3N+1 ， 为3N 代表目标值在这一位没贡献， 3N+1 代表目标值在这一位有贡献 (=1) ，然后将所有有贡献的位|起来就是结果。
注意 最高位 为符号位，如果最后判断得到最高位 有贡献，那么应该 是负数，且为 res - (1 << 31)或者 res - (2 ^{31})。举个例子， 1010 为 -6 ，0010为2 ，-6 = 2 - (1<<3) - 2 - (2^3)
题解
class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for i in range(0, 32): # 统计 所有数字中 第 i 位的情况 temp = 0 for num in nums: temp += num >> i & 1 # 次处先不判断符号位, 即 i= 31 的时候 if temp % 3 != 0 and i != 31: # 将该位置 1 res = res | (1 << i) # 最后 如果temp 不是 3 的倍数，说明是负数 if temp % 3 != 0: res = res - (1 << 31) return res