题目网址：

---

题目描述：

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

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

找一个出现次数仅为一次的数，O(n)时间

---

题目解答：

初步的想法就是把array排序，然后从前往后配对，遇见不一样的就是第一个数是出现一次的，考虑边界条件（array长度是1或者最后一个数是要找的数）

def singleNumber(self, A):        A.sort()        if len(A) == 1:            return A[0]        for i in A:            if i%2 == 1:                if A[i] != A[i-1]:                    return A[i-1]                else:                    pass                    print "hey bitch:" + "A[" + str(i) + "] = " + str(A[i]) + "\n"            elif i == len(A):                return A[len(A)]

很可惜这玩意超时了。然后我就想了，list是个超级低效的数据结构，何不用dict，于是：

#A.sort()        D = {}        for i in A:            if i not in D:                D[i] = 1            else:                D[i] = D[i]+1        for i in D:            if D[i] == 1:                return i

空间、时间复杂度O(n),其实sort不sort差不多,但是sort的时间复杂度为O(nlogn)。但是，题目里说了，怎么才能少用或者不用memory?于是:

A.sort()        while len(A) != 1:            a = A.pop()             b = A.pop()            if a == b:                pass            else:                return a        return A[0]

用了O(1)空间，但是时间又涨到O(nlogn)，绞尽脑汁，想不出来啊。于是翻了翻评论，原来还有位运算这回事儿：

if len(A) == 1:            return A[0]        else:            for a in A[1:]:                A[0] = a^A[0]             return A[0]

这才是真正满足题目要求的解，虽然上面的代码都过了吧

ps: 0 = x XOR x  

---

Dec 6,2014更新

网上发现了一个叫做词典翻转的玩意儿，感觉挺好玩的，改编一下上面的代码如下：

def singleNumber(self,A)        D = {}        for i in A:            if i not in D:                D[i] = 1            else:                D[i] = D[i]+1        #D_r = dict((v,k) for k,v in D.iteritems())        D_r = dict([(v,k) for k,v in D.iteritems()])        return D_r[1]

 AC!

其中被注释的那一行是用的生成器表达式，下面一行用的是表推导（就是快速生成表的一种方法）