代碼涉及的python3和python2之間的區(qū)別僅僅在于print函數(shù)是否有括號，在挪缶粒客網(wǎng)的python2環(huán)境下不需要print任何輸出蓖康，因此不影響。
方法一：使用python內(nèi)collections模塊的Counter函數(shù)
#使用python內(nèi)collections模塊的Counter函數(shù)
# -*- coding:utf-8 -*-
import collections
class Solution:
# 返回[a,b] 其中ab是出現(xiàn)一次的兩個數(shù)字
def FindNumsAppearOnce(self, array):
# write code here
resultList = []
key_dict = {}
key_dict = collections.Counter(array)
for key, value in key_dict.items():
if value == 1:
resultList.append(key)
return resultList
當(dāng)然澳眷，劍指offer上還有另外一個條件：要求時間復(fù)雜度是o(n), 空間復(fù)雜度是o(1)。上面的程序需要一個額外的字典來存儲每個字母出現(xiàn)的次數(shù)蛉艾，因此明顯不符合空間復(fù)雜度o(1)的要求钳踊。
方法二：使用位運(yùn)算
對于這個問題，我們先考慮一個簡化版的假設(shè)勿侯。若一個整形數(shù)組里拓瞪，除了一個數(shù)字，其它數(shù)字都出現(xiàn)了兩次助琐，請找出這個只出現(xiàn)一次的數(shù)字祭埂。此時，可以用異或的思維兵钮，使得所有出現(xiàn)兩次的數(shù)字在異或操作中變成0.
因此蛆橡，本題將數(shù)組分成兩個子數(shù)組，使得每個子數(shù)組中只包含一個只出現(xiàn)一次的數(shù)字掘譬。那么如何將數(shù)組分成兩個我們想要的子數(shù)組呢泰演？
若我們將原數(shù)組的所有元素都進(jìn)行異或操作，那么結(jié)果肯定是不相同的那兩個元素的異或結(jié)果（如[1, 2, 4, 6, 2, 1]屁药，異或結(jié)果為0000 0100 ^ 0000 0110 = 0000 0010 = 2）粥血，說明不相同的兩個元素在倒數(shù)第二位一定不同（一個1另一個是0）柏锄，因此可以按照這一位的數(shù)字將原數(shù)組分成兩個子數(shù)組酿箭，第一個子數(shù)組中倒數(shù)第二位是1复亏，第二個子數(shù)組中倒數(shù)第二位是0。當(dāng)然異或結(jié)果可能不止一個1缭嫡，可以從前往后數(shù)以第一個1來劃分缔御，也可以從后往前數(shù)。由于相同的兩個元素倒數(shù)第二位一定相同妇蛀，因此相同的兩個元素肯定在同一個子數(shù)組里耕突。
接下來的代碼以{2, 4, 3, 6, 3, 2, 5, 5}為例，不相同的兩位數(shù)字是4评架， 6眷茁，異或結(jié)果為0000 0010，因此以倒數(shù)第二位為標(biāo)準(zhǔn)纵诞，將原數(shù)組中的所有元素分為兩個子數(shù)組上祈。第一個子數(shù)組的倒數(shù)第二位是1，{2, 2, 3, 3, 6}, 第二個子數(shù)組的倒數(shù)第二位是0浙芙， {4登刺， 5， 5}嗡呼。
class Solution:
# 返回[a, b], 其中a ,b 是其中只出現(xiàn)一次的兩個數(shù)字
def FindNumsAppearOnce(self, array):
outputRes = []
arrayOfOne = []
arrayOfZero = []
temp = array[0]
flagNum = 1
# 循環(huán)纸俭，使得整個數(shù)組的每個元素都參與異或，從而凸顯出只出現(xiàn)一次的兩個元素的異或值
for i in range(1, len(array)):
temp ^= array[i] #循環(huán)完成之后的temp南窗，即為有標(biāo)志位的二進(jìn)制數(shù), 依據(jù)其中1的位置將數(shù)組分為兩個子數(shù)組
#print("temp = ", temp)
#構(gòu)造只有一個1的二進(jìn)制數(shù)揍很，這個1和temp中右起第一個1位置一致
flagNum = temp & (-temp)
#print("flagNum = ", bin(flagNum))
#劃分兩個子數(shù)組，分別讓每個元素都和構(gòu)造的有標(biāo)志位的二進(jìn)制數(shù)進(jìn)行按位與操作
for j in range(0, len(array)):
if array[j] & flagNum == 0:
arrayOfZero.append(array[j])
else:
arrayOfOne.append(array[j])
#print(arrayOfZero)
#print(arrayOfOne)
# 此時已經(jīng)將原數(shù)組按照標(biāo)志位分成了兩個子數(shù)組
temp = arrayOfZero[0]
for m in range(1, len(arrayOfZero)):
#print(arrayOfZero[m])
temp ^= arrayOfZero[m]
#print("temp = ", temp)
outputRes.append(temp)
temp = arrayOfOne[0]
for n in range(1, len(arrayOfOne)):
temp ^= arrayOfOne[n]
outputRes.append(temp)
return outputRes
但是這里用了兩個額外的數(shù)組來存儲兩個子數(shù)組万伤，可以省略掉存儲子數(shù)組這一步窒悔，直接計(jì)算子數(shù)組的異或值。具體代碼如下：
class Solution:
# 返回[a, b], 其中a ,b 是其中只出現(xiàn)一次的兩個數(shù)字
def FindNumsAppearOnce(self, array):
outputRes = []
arrayOfOne = []
arrayOfZero = []
outputA = 0
outputB = 0
temp = array[0]
flagNum = 1
# 循環(huán)壕翩，使得整個數(shù)組的每個元素都參與異或蛉迹，從而凸顯出只出現(xiàn)一次的兩個元素的異或值
for i in range(1, len(array)):
temp ^= array[i] #循環(huán)完成之后的temp，即為有標(biāo)志位的二進(jìn)制數(shù), 依據(jù)其中1的位置將數(shù)組分為兩個子數(shù)組
#print("temp = ", temp)
#構(gòu)造只有一個1的二進(jìn)制數(shù)放妈，這個1和temp中右起第一個1位置一致
flagNum = temp & (-temp)
#print("flagNum = ", bin(flagNum))
#劃分兩個子數(shù)組北救，分別讓每個元素都和構(gòu)造的有標(biāo)志位的二進(jìn)制數(shù)進(jìn)行按位與操作
for j in range(0, len(array)):
if array[j] & flagNum == 0:
#arrayOfZero.append(array[j])
outputB ^= array[j] #這里為outputA和outputB設(shè)置初始值為0并不影響最終的異或結(jié)果，但是不能設(shè)置為1
else:
#arrayOfOne.append(array[j])
outputA ^= array[j]
outputRes.append(outputA)
outputRes.append(outputB)
return outputRes
2. 修改題目
在一個數(shù)組中除一個數(shù)字只出現(xiàn)一次之外芜抒，其它數(shù)字都出現(xiàn)了三次珍策。請找出那個只出現(xiàn)一次的數(shù)字。
先不考慮只出現(xiàn)一次的那個數(shù)字宅倒，若當(dāng)前數(shù)組中所有數(shù)字都出現(xiàn)了3次攘宙，若以32位來表示每個數(shù)字，如下面示例。
{3, 3, 3}--二進(jìn)制表示如下：
{00000000 00000000 00000000 00000011,
? 00000000 00000000 00000000 00000011蹭劈，
? 00000000 00000000 00000000 00000011}
如果將二進(jìn)制表示的每一位分別求和疗绣，則和都可以被3整除。上面3個數(shù)的和為：
? 00000000 00000000 00000000 00000033
若此時有一個數(shù)字只出現(xiàn)了一次铺韧，
{3, 3, 3, 4}
{00000000 00000000 00000000 00000011,
? 00000000 00000000 00000000 00000011多矮，
? 00000000 00000000 00000000 00000011
? 00000000 00000000 00000000 00000100}, 其和為：
? 00000000 00000000 00000000 00000133}
其中，倒數(shù)第一位和倒數(shù)第二位都為3哈打，可以被3整除塔逃，說明只出現(xiàn)了一次的那個數(shù)字這兩位都是0。倒數(shù)第三位是1料仗， 不可以被3整除湾盗，說明只出現(xiàn)了一次的那個數(shù)字這一位是1。
按照以上的想法來看立轧，代碼如下：
class Solution(object):
def FindNumAppearOnce(self, array):
result = [0] * 32 #最后這個只出現(xiàn)一次的數(shù)字的二進(jìn)制形式是一個字符串
#array = list(map(bin, array))
flag = 1
for i in range(31, 0, -1):
#print("flag = ", bin(flag))
for j in range(0, len(array)):
#print("array[%s] = %s" %(j, array[j]))
if array[j] & flag != 0: #若當(dāng)前數(shù)字當(dāng)前位等于1格粪，則給result的當(dāng)前位加1
result[i] += 1
#print("result[%s] = %s" %(i, result[i]))
flag = flag << 1
if result[i] % 3 == 0:
result[i] = 0
else:
result[i] = 1
#print("reault = ", result)
result = list(map(str, result))
outputResult = "".join(result)
print(int(outputResult, 2)) #二進(jìn)制字符串轉(zhuǎn)十進(jìn)制，輸出4
if __name__ == "__main__":
s = Solution()
outputRes = []
inputArray = [3, 3, 3, 4]
outputRes = s.FindNumAppearOnce(inputArray)
