LeetCode 136. 只出现一次的数字 | Python

思路：位运算

说明位运算方法的实现前，我们先看下题目，在说明后面，题目要求【算法应具有线性事件复杂度，不需要额外的空间】。如果没有这个要求，我们能想到方法可能有以下几种：

• 使用集合存储，遍历数组，当数字未在集合中时，先添加到集合中，当存在这个数字时，则从集合中删除，因为题目中已经说明，只有 1 个数字时重复的，那么最后集合中剩下的就是该数字。
• 使用哈希表存储数字以及数字出现的次数，遍历数组，维护哈希表。最终遍历哈希表，数字出现次数为 1 的就是所求得数字。
• （这个思路来自官方题解），同样使用集合存储数字，但是这里涉及到普通的运算。集合存储数组的元素，因为集合中不会出现重复的数字，而数组中只有一个数字是重复的，当集合中的数字和的两倍减去原数组中所有元素之和，那么两者所得的结果就是这个数字。

以上方法都能够解决该问题，但是题意要求【算法应具有线性事件复杂度，不需要额外的空间】。那么这三个方法都不满足条件。

本篇幅使用的是位运算，关于位运算的使用，之前在 LeetCode 面试题56 - I. 数组中数字出现的次数 | Python 曾经使用过，这里再重新说一下异或的性质：二进制位同一位相同则为 0，不同则为 1。关于异或的规律：

• 任何数与自身异或结果为 0。
• 任何数与 0 异或结果为本身。

同时，异或满足交换律、结合律（数学符号：⊕）

• 交换律： a ⊕ b = b ⊕ a
• 结合律： a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

先定义返回变量为 0，对数组变量依次进行异或，那么根据上面的规律，我们就可以计算出题目中所说那个不重复的数字。

具体的代码实现如下。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
 # 任何数与 0 异或结果为自身
 # 这里定义变量 0，对数组所有元素进行异或时
 # 任何数与自身异或结果为 0
 # 那么最终剩下的就是单独的数字
 res = 0
 for x in nums:
     res ^= x
 return res