难度: 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 - 1nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次运行时间: 25 ms
内存: 17.7 MB
class Solution:
def singleNumber(self, nums: List[int]) -> int:
"""
1. 遍历数组中的每个元素，对于每个元素，遍历其二进制表示的每一位。
2. 创建一个长度为32的数组（考虑到整数的标准长度），用于统计所有数字在每一位上1出现的次数。
3. 对于数组中的每个数，将其在每一位上的1加到对应的计数器上。
4. 遍历这个长度为32的计数器数组，对于每一位的计数，因为除了那个唯一的元素外，其他元素都出现3次，所以如果某一位上的计数是3的倍数，则那个唯一的元素在这一位上是0；否则是1。
5. 将这些位组合起来，就得到了那个只出现一次的数。
"""
count = [0] * 32
for n in nums:
for i in range(32):
count[i] += n & 1
n >>= 1
result= 0
for i in range(32):
if count[i] % 3 != 0:
if i == 31: # 负数情况
result -= (1 << i)
else:
result = result | (1 << i)
return result
该题解采用位运算和计数的方法来找到只出现一次的元素。首先，创建一个长度为32的数组来统计每个整数的每一位上1出现的次数。接着，遍历输入数组，对每个数字，通过位运算统计其每一位的1的数量，并更新到计数数组中。由于除了一个元素之外，其他元素都出现三次，如果某位的计数能被3整除，则目标元素在该位为0；否则为1。最后，根据这些位的信息重构出只出现一次的数字。特别注意的是，对于32位整数的最高位（符号位），需要特殊处理，以区分正负数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 创建一个长度为32的数组以存储每位的1的计数
count = [0] * 32
for n in nums:
for i in range(32): # 遍历每个数字的每一位
count[i] += n & 1 # 计算当前最低位是否为1并累加到计数器
n >>= 1 # 右移数字，准备检查下一位
result = 0
for i in range(32): # 遍历每一位
if count[i] % 3 != 0: # 如果计数不是3的倍数，说明目标数字在这一位是1
if i == 31: # 对最高位进行符号位处理
result -= (1 << i)
else:
result = result | (1 << i) # 使用位或操作将结果中的相应位设为1
return result
在位运算解法中，选择32位整数数组来存储每一位的计数是因为在大多数现代计算机系统中，整数通常表示为32位的二进制数。这包括正数和负数（使用补码形式）。因此，为了准确并全面地统计每一个数字的每一位上1出现的次数，我们使用了一个长度为32的数组。每个元素对应一个二进制位的计数，确保可以处理任何32位整数的所有位。
在32位整数中，最高位（第31位）是符号位，用来表示整数的正负。在统计和重构该位时需要特别注意，因为它决定了数字的符号。如果计算出的最高位为1，它不仅简单表示该位是1，而是表示这是一个负数。因此，在重构最终结果时，如果发现第31位上的计数不能被3整除，我们需要通过减法（而不是简单的位或操作）添加一个负数位权重，即`result -= (1 << 31)`。这样处理是为了正确反映符号位的负值效果，保持整数的补码表示正确。
题目条件指出，除了一个元素仅出现一次外，其他每个元素都恰好出现三次。这意味着如果我们统计所有数字中每一位上1出现的次数，除了单独出现一次的数字贡献的1外，其他的1的总数一定是3的倍数。因此，对于任何一个位，如果该位上1的总计数不是3的倍数，那么剩余的1（即计数模3的结果）必然来源于那个只出现一次的数字。如果是3的倍数，则说明所有贡献该位的1都完美抵消了，目标数字在该位上的值为0。这是根据题目的特殊条件和整数的位操作特性推导出的逻辑。