136。只出现一次的数字题目来源：https://leetcode-cn.com/problems/single-number每个元素出现两次，只是元素只出现一次。找到只出现一次的元素。说明：您的算法应该具有线性时间复杂度。你能在不使用额外空间的情况下做到吗？例1：输入：[2,2,1]输出：1例2：输入：[4,1,2,1,2]输出：4解题思路：位运算说明位运算执行前方法，我们先看标题。描述之后，标题要求【算法应该具有线性事件复杂度，不需要额外的空间】。如果没有这个需求，我们可以想到以下方法：使用集合存储，遍历数组，当数字不在集合中时，先加入到集合中，当数字存在时从集合中删除，因为题目中已经解释过，如果只有一个数重复，那么最后一组剩下的就是这个数。使用哈希表存储数字和数字出现的次数，遍历数组，维护哈希表。最后遍历哈希表，将出现次数为1的数作为得到的数。（这个思路来自于官方的题解），也是用集合来存储数字，不过这涉及到普通的操作。集合存储数组的元素，因为集合中不会有重复的数字，数组中只有一个数字重复。当集合中的数之和是原数组中所有元素之和的两倍时，则两者的结果就是这个数。以上方法都可以解决这道题，但是题意要求【算法应该是线性事件复杂度，不需要额外的空间】。那么这三种方法都不满足条件。本文使用位运算。关于位运算的使用，我之前在LeetCode面试题56-I.数字在数组中出现的次数|Python，这里我再说一下异或的本质：同一个二进制位相同则为0，不同则为1。关于XOR的定律：任何数字与它自己异或的结果都是0。任何数字与0的异或结果都是它自己。同时异或满足交换律和结合律（数学符号：⊕）commutativelaw:a⊕b=b⊕aassociativelaw:a⊕(b⊕c)=(a⊕b)⊕c首先定义返回变量为0，依次对数组变量进行异或，然后根据上面的规则，我们就可以计算出题目中提到的不重复数。具体代码实现如下。代码实现类解决方案：defsingleNumber(self,nums:List[int])->int:#任意数与0的异或结果就是它自己#这里定义变量0，当对数组的所有元素进行异或时#任意数和它自己异或结果为0#那么最后剩下的数就是一个数res=0forxinnums:res^=xreturnres得到结果以上是对数组的元素依次进行异或位运算异或的性质和规律，进而解决《136. 只出现一次的数字》问题的主要内容。欢迎关注微信公众号《书所集录》
