題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字昼窗。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)阁将。
這道題如果沒(méi)有想到用異或來(lái)解決的話膏秫，可能就比較不容易做出來(lái)了。異或操作有一個(gè)好處在于做盅，兩個(gè)相同的數(shù)異或的結(jié)果是0缤削，并且異或操作是滿足交換率的，所以異或的順序?qū)Y(jié)果不會(huì)有影響吹榴。
想到這一點(diǎn)的話亭敢，就可以知道，我們首先遍歷一遍整個(gè)數(shù)組图筹，得到所有數(shù)字的異或結(jié)果帅刀，這個(gè)結(jié)果相當(dāng)于是兩個(gè)只出現(xiàn)一次的數(shù)字的異或結(jié)果让腹，并且這個(gè)結(jié)果一定不是0（因?yàn)檫@兩個(gè)數(shù)不一樣）。
假設(shè)這個(gè)異或的結(jié)果中扣溺，第k位為1骇窍，我們根據(jù)第k位是不是1為標(biāo)準(zhǔn)，把原數(shù)組分成兩個(gè)子數(shù)組锥余，一個(gè)子數(shù)組中每個(gè)數(shù)字的第k位都是1腹纳，另一個(gè)子子數(shù)組中每個(gè)數(shù)字的第k位都是0，這樣驱犹，兩個(gè)只出現(xiàn)一次的數(shù)分別被分到不同的子數(shù)組中嘲恍，并且每對(duì)相同的數(shù)字都會(huì)被分配到同一個(gè)子數(shù)組中。
針對(duì)每一個(gè)子數(shù)組雄驹，再利用異或的方法佃牛，即可找到那個(gè)只出現(xiàn)一次的數(shù)字。
#encoding=utf8
'''
題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外医舆，其他的數(shù)字都出現(xiàn)了兩次俘侠。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
要求時(shí)間復(fù)雜度是O(n)彬向，空間復(fù)雜度是O(1)兼贡。
'''
def find_two_unique_num(num_list):
result = 0
for num in num_list:
result ^= num
lowbit = find_lowest_bit(result)
result_1 = 0
result_2 = 0
for num in num_list:
if num & lowbit != 0:
result_1 ^= num
else:
result_2 ^= num
return (result_1, result_2)
def find_lowest_bit(num):
index = 0
while num & 1 == 0:
num = num >> 1
index = 1
return 1 << index
if __name__ == '__main__':
num_list_1 = [2, 2, 1, 3]
num_list_2 = [2, 4, 3, 6, 3, 2, 5, 5]
print find_two_unique_num(num_list_1)
print find_two_unique_num(num_list_2)
