难度: Medium
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2] 输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100] 输出：100
提示：
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
注意：本题与主站 137 题相同：https://leetcode-cn.com/problems/single-number-ii/
运行时间: 22 ms
内存: 17.7 MB
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# no extra space? Then sorting in linear time complexity
# pivot sort
counts = {}
for n in nums:
c = counts.get(n, 0)
counts[n] = c+1
for k in counts.keys():
if counts[k]==1:
return k
return nums[0]
该题解采用了哈希表来记录数组中每个元素出现的次数。首先遍历输入数组 nums，利用哈希表 counts 记录每个元素出现的次数。在第一次遍历完成后，再次遍历哈希表，查找只出现一次的元素并返回。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 使用哈希表来记录每个元素出现的次数
counts = {}
for n in nums:
# 获取当前元素的计数，如果未记录则为0
c = counts.get(n, 0)
# 更新哈希表中的计数
counts[n] = c + 1
# 遍历哈希表，找到只出现一次的元素
for k in counts.keys():
if counts[k] == 1:
return k
# 默认返回第一个元素（理论上不会执行到这里，因为题目保证存在只出现一次的元素）
return nums[0]
题解中默认返回数组的第一个元素作为异常处理实际上是一个理论上不应发生的情况，因为题目描述保证了至少有一个数字只出现一次。如果没有这样的保证，或者错误地应用该代码到一个所有元素都至少出现两次的数组，该默认返回将导致错误的结果。此外，如果数组为空，直接访问第一个元素会引发错误。
题解中的哈希表解法主要适用于静态数组，即数组中的元素和它们的出现次数在遍历之前已经确定。如果数组中的元素出现次数是动态变化的情况（例如，数组元素在遍历过程中可能被修改），则需要采取额外的措施来确保准确性。这包括频繁更新哈希表来反映最新的出现次数，或使用更复杂的数据结构（如跳表或平衡二叉树）来维护元素及其动态变化的计数。