leetcode【165】Single Number（关于异或）

写在最前面：除了介绍这道题本身以外，会讲一讲python中的异或

leetcode【165】Single Number

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1] Output: 1

Example 2:

Input: [4,1,2,1,2] Output: 4

这道题用^比较方便，首先介绍一下^

下面看两个数：

a = 60

b = 13

a ^ b = 49

0011 1100 0000 1101 0011 0001

^ 的原理是相同为0，相异为1

那么根据这个原理，0和任何数异或，要么是0，要么是任何数本身，所以这个性质决定了只有0能作为初始进行异或的数

由于题目给定的列表只包含唯一一个只出现一次的数，我们的目的是找到它

大家还应该知道一个重要的常识，^ 是有交换律的

a = [3,2,7,6,6,4,3,2,7,4] b = [3,2,6,6,7,4,3,2,7,4] res = 0 ses = 0 for i in range (len(a)): res ^= a[i] for i in range (len(b)): ses ^= b[i] print(res,ses) 0 0

而且成对出现的数，不管你怎么打乱顺序，最后结果一定是0

我们用0先和第一个异或，为什么不用其他数，因为要保证从第一个列表中的数开始异或

假设列表[a,c,b,a,d,c,b]遍历异或后实际上是进行这样的运算：

a ^ c ^ b ^ a ^ d ^ c ^ b

交换异或即

(a ^ a) ^ (b ^ b) ^ (c ^ c) ^ d

0和那个唯一的数异或还是本身，所以最后return了那个唯一的数

我看了下网上对这样操作的原理讲的都不清不楚，作为一个较真的博主，我还是希望能把我写的东西明明白白的告诉大家，才对得起原创二字

下面是解题代码：

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ length = len(nums) res = 0 for i in range(length): res ^= nums[i] return res

今天就到这儿，满足