Contents

原题地址:single-number

题目翻译如下:

给定一个整数数组,其中有一个整数仅出现一次,其余每一个整数都恰好出现了两次。找出这一整数。
注:算法要求线性时间复杂度,不使用额外的存储空间。

一个最初的想法是,利用列表的sort方法来将列表进行排序,之后遍历列表,判断已排序的列表中每一个元素的前后是否存在相同元素,若都不存在,则为我们要找的数。

实际提交时,运行时间超出限制。后来想起来列表的sort方法是O(nlogn)复杂度的,故不行。

在此找到一篇wiki:Time Complexity,列出了CPython(即常见官方实现)中各种内置数据结构的方法的复杂度。

后来从讨论区看了别人的实现,才学到可以用按位操作符XOR来实现。这里采用的主要想法是:我们可以用一个初始值为0的变量r来作记录,与列表中的每一个数都做异或运算。对于存在两次的数,做了两次异或后相互作用抵消,仍能将变量r恢复为原来的值。这样当所有数都与r做过异或运算后,r最后的值就记录了那个仅仅出现一次的数。

用规范化的说法,算法可行的原因是基于异或位运算的两条基本原理:

自反律:(a ⊕ b) ⊕ b = a
交换律:a ⊕ b ⊕ c = a ⊕ c ⊕ b

第一条自反律保证了,只要两个相同的数都与r做异或,r不受影响。第二条交换律保证了这两个数不必先后紧跟着与r做运算,中间夹杂别的数先来运算也是可以的,只要在整个运算过程中这两个相同的数都算过,第一条的结果仍不受影响。

代码实现如下,A是整数列表。代码非常简洁:

1
2
3
4
5
def singleNumber(A):
r = 0
for i in A:
r ^= i
return r

Contents