136. 只出现一次的数字
题目来源：https://leetcode-cn.com/problems/single-number
题目
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
解题思路
思路：位运算
说明位运算方法的实现前，我们先看下题目，在说明后面，题目要求【算法应具有线性事件复杂度，不需要额外的空间】。如果没有这个要求，我们能想到方法可能有以下几种：
- 使用集合存储，遍历数组，当数字未在集合中时，先添加到集合中，当存在这个数字时，则从集合中删除，因为题目中已经说明，只有 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
实现结果
实现结果
以上就是根据位运算异或的性质规律，对数组元素依次进行异或，进而解决《136. 只出现一次的数字》问题的主要内容。
欢迎关注微信公众号《书所集录》
