leetcode-136. 只出现一次的数字

LeetCode 136. 只出现一次的数字

题目给出了一个整数数组，其中只有一个元素出现一次，其余元素都恰好出现两次，要求找出这个只出现一次的数字。

1. 哈希表统计

最容易想到的方法就是使用哈希表，记录每个数字出现的次数。

先遍历一遍数组，将数字作为键，出现次数作为值存入哈希表。统计完成后，再遍历哈希表，找到出现次数为 1 的数字即可。

Python 代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hs=dict()
        for i in nums:
            hs[i]=hs.get(i,0)+1
        for key in hs.keys():
            if hs[key]==1:
                return key

这份代码虽然使用了两个 for 循环，但它们是依次执行的，而不是相互嵌套。

因此，在哈希表操作平均为常数时间的情况下，整体时间复杂度仍然是 $O(n)$。

不过，哈希表需要额外保存每个数字的出现次数，最坏情况下需要 $O(n)$ 的空间。

而题目要求使用线性时间复杂度和常数额外空间完成，因此还需要考虑其他方法。

2. 利用异或运算优化

如果不使用哈希表，还有什么办法能够让出现两次的数字相互抵消，最后只留下出现一次的数字呢？

这里可以利用异或运算（XOR）。

异或是一种位运算，在 Python 中使用 ^ 表示。它会逐位比较两个数的二进制表示：

• 对应的两个二进制位不同，结果为 1。
• 对应的两个二进制位相同，结果为 0。

异或有几个重要性质，正好适合这道题。

性质一：任何数与 0 异或，结果仍然是它本身。

例如，数字 9 的二进制为 1001：

  1001
^ 0000
------
  1001

每一位都保持不变，因此结果仍然是 9。

性质二：两个相同的数异或，结果为 0。

例如：

  1001
^ 1001
------
  0000

由于每一位都相同，异或之后全部变成 0。

性质三：异或满足交换律和结合律。

也就是说，异或运算可以调整计算顺序，而不会影响最终结果。

例如：

因为两个 x 会相互抵消，剩下的就是 y。

3. 将异或应用到数组中

理解了这几个性质，解题思路就比较明确了。

题目保证数组中只有一个数字出现一次，其他数字都出现两次。

因此，我们可以将数组中的所有元素依次进行异或运算。

例如：

nums = [4, 1, 2, 1, 2]

将所有元素异或：

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

由于相同的数字会相互抵消，最后留下的就是只出现一次的数字。

实现时，只需要创建一个变量 res，初始值设为 0，然后依次与数组中的每个元素进行异或。

Python 代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res=0
        for i in nums:
            res=res^i
        return res

这样就不需要额外创建哈希表了。

整个过程只遍历一次数组，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

4. 总结

两种方法都能在线性时间内找到只出现一次的数字，但额外空间开销不同。

哈希表的思路比较直观，适合统计元素的出现次数；异或则利用相同数字可以相互抵消的性质，不需要额外存储这些统计信息。

这道题的关键在于发现题目中“其他数字都恰好出现两次”这个条件，并将它与异或运算的性质联系起来。

如果没有这个条件，就不能直接通过异或所有元素来确定只出现一次的数字。