PRoblem 1：一個數組中有一個數字a只出現一次，其他數字都出現了兩次。請找出這個只出現一次的數字？
考察知識點：異或運算
思路：比如數字 b^b = 0
a^0 = a
因此，可以將數組中的所有數字進行異或，而最終異或的結果即為所求只出現一次的數字a.
代碼：
1 def SingleNumber1(Array):2 ret = 03 for i in Array:4 ret ^= i5 return ret
==========================================================
Problem 2：一個數組中有一個數字a只出現一次，其他數字都出現了三次。請找出這個只出現一次的數字？
考察知識點：位運算
解法一：
考慮用統計的思路來解這道題，如果一個數出現了三次就消掉，int的32個位都是由0/1組成的，所以將所有數的對應位加起來，
再將各位的統計和對3取模，最終剩下的結果就是要找出的數。
例如：數組 [4 7 4 4](這里為了方便，我們取int的最后四位)
4 0 1 0 0
7 0 1 1 1
4 0 1 0 0
4 0 1 0 0
Sum 0 4 1 1
Sum%3 0 1 1 1
最后Sum%3得到的結果0111即7，就是我們所要求的Single Number
代碼：
1 def SingleNumber2_1(Array): 2 ret = 0 3 for i in range(0,32): 4 c = 0 5 d = 1 << i 6 for j in range(0, len(Array)): 7 if Array[j] & d: 8 c += 1 9 if c % 3:10 ret |= d;11 return ret
解法二：
考慮每一位的統計值，如果累加到3就歸為0，則只會有0/1/2三種情況，所以將大小為32的int數組改為只用兩個int即可。
第一個int的第i位為0/1代表第i位當前累加有0/1個 1 ，第二個int的第i位為1代表第i位當前累加有2。
當int1和int2中的第i位均為1時，我們將他們都清零。
例如：數組 [4 7 4 4](這里為了方便，我們取int的最后四位)
4 0 1 0 0
one 0 1 0 0
two 0 0 0 0
=====================
7 0 1 1 1
one 0 0 1 1
two 0 1 0 0
=====================
4 0 1 0 0
one 0 0 0 0
two 0 0 1 1
=====================
4 0 1 0 0
one 0 1 0 0
two 0 0 0 0
=====================
代碼：
1 def SingleNumber2_2(Array): 2 one = 0 3 two = 0 4 three = 0 5 for i in range(0, len(Array)): 6 two |= (one & Array[i]) 7 one ^= Array[i] 8 three = one & two 9 two -= three10 one -= three11 return one
==========================================================
Problem 3：一個數組中有兩個數字a、b只出現一次，其他數字都出現了兩次。請找出這兩個只出現一次的數字？
思路：若將數組中的所以數字進行異或，那么最終結果為 a ^ b
由于a != b，可以知道a ^ b != 0.即結果肯定有一位為1.
根據那一位，我們知道a，b的那一位肯定一個是0，一個是1.
我們找到為1的那一位i，根據i位為0/1將數組分成兩組，即可將a, b分開。
因此，我們要解決的是兩個Problem 1.
代碼：
1 def SingleNumber3(Array): 2 ret = 0 3 for i in range(0,len(Array)): 4 ret ^= Array[i] 5 pos = 0 6 for j in range(0,32): 7 if (ret>>j) & 1: 8 pos = j 9 break10 sub1,sub2 = split(Array,pos)11 single1 = SingleNumber1(sub1)12 single2 = SingleNumber1(sub2)13 return single1,single214 15 def split(Array, pos):16 sub1 = []17 sub2 = []18 for i in range(0,len(Array)):19 if (Array[i]>>pos) & 1:20 sub1.append(Array[i])21 else:22 sub2.append(Array[i])23 return sub1,sub2 1 def SingleNumber3(Array): 2 ret = 0 3 for i in range(0,len(Array)): 4 ret ^= Array[i] 5 pos = 0 6 for j in range(0,32): 7 if (ret>>i) & 1: 8 pos = i 9 break10 sub1,sub2 = split(Array,pos)11 single1 = SingleNumber1(sub1)12 single2 = SingleNumber1(sub2)13 return single1,single214 15 def split(Array, pos):16 sub1 = []17 sub2 = []18 for i in range(0,len(Array)):19 if (Array[i]>>pos) & 1:20 sub1.append(Array[i])21 else:22 sub2.append(Array[i])23 return sub1,sub2
==========================================================
Problem 4：一個數組中有一個數字a只出現一次，其他數字都出現了K次。請找出這個只出現一次的數字？
考察知識點：位運算 and 分情況解決
① K % 2 == 0
基本思路類似于Problem 1
② K % 2 == 1
基本思路類似于Problem 2
代碼：
1 def SingleNumber4(Array, k):2 if k % 2 == 0:3 ret = SingleNumber1(Array)4 else:5 ret = SingleNumber2_1(Array)6 return ret
==========================================================
Problem 5：一個數組中有三個數字a、b、c只出現一次，其他數字都出現了兩次。請找出這三個只出現一次的數字？
思路：此處轉載自：http://zhedahht.blog.163.com/blog/static/25411174201283084246412/
如果我們把數組中所有數字都異或，那最終的結果（記為x）就是a、b、c三個數字的異或結果（x=a^b^c）。其他出現了兩次的數字在異或運算中相互抵消了。
我們可以證明異或的結果x不可能是a、b、c三個互不相同的數字中的任何一個。
我們用反證法證明。假設x等于a、b、c中的某一個。比如x等于a，也就是a=a^b^c。因此b^c等于0，即b等于c。這與a、b、c是三個互不相同的三個數相矛盾。
由于x與a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。
我們定義一個函數f(n)，它的結果是保留數字n的二進制表示中的最后一位1，而把其他所有位都變成0。比如十進制6表示成二進制是0110，
因此f(6)的結果為2（二進制為0010）。f(x^a)、f(x^b)、f(x^c)的結果均不等于0。
接著我們考慮f(x^a)^f(x^b)^f(x^c)的結果。由于對于非0的n，f(n)的結果的二進制表示中只有一個數位是1，因此f(x^a)^f(x^b)^f(x^c)的結果肯定不為0。
于是f(x^a)^f(x^b)^f(x^c)的結果的二進制中至少有一位是1。假設最后一位是1的位是第m位。那么x^a、x^b、x^c的結果中，有一個或者三個數字的第m位是1。
我們使用反正法證明不可能三個數字第m位都是1.
如果x^a、x^b、x^c的第m位都是1，那么a、b、c三個數字的第m位和x的第m位都相反，因此a、b、c三個數字的第m位相同。如果a、b、c三個數字的第m位都
是0，x=a^b^c結果的第m位是0。由于x和a兩個數字的第m位都是0，x^a結果的第m位應該是0。同理可以證明x^b、x^c第m位都是0。這與我們的假設矛盾。
如果a、b、c三個數字的第m位都是1，x=a^b^c結果的第m位是1。由于x和a兩個數字的第m位都是1，x^a結果的第m位應該是0。
同理可以證明x^b、x^c第m位都是0。這還是與我們的假設矛盾。
因此x^a、x^b、x^c三個數字中，只有一個數字的第m位是1。于是我們找到了能夠區分a、b、c三個數字的標準。
=============================================================
這里我們需要注意上面只是在已知ａ，ｂ，ｃ的情況下的理論證明，具體編程則有些不一樣：
我們先求得 x = a ^ b ^ c
我們可以將x分別與數組中的元素再進行一次異或，得到一個新的數組，但是并沒有改變數組的特性。
比如與數組中有兩個相等的數字d
那么經過處理之后這兩個數還是相等的，只不過結果為x ^ d
==============================================================
這樣我們可以將數組分成兩部分，這里假設a的m位為1。
則兩個子數組分別為：sub1：包含a == Problem 1
sub2：包含b, c == Problem２
代碼：
1 def SingleNumber5(Array): 2 x = 0 3 for i in range(0,len(Array)): 4 x ^= Array[i] 5 newArray = [] 6 for j in range(0,len(Array)): 7 newArray.append(x^Array[j]) 8 lastOneArrary = func(newArray) 9 ret = 010 for i in range(0,len(lastOneArrary)):11 ret ^= lastOneArrary[i]12 pos = 013 for j in range(0,32):14 if (ret>>j) & 1:15 pos = j16 break17 sub1, sub2 = split(Array,pos)18 print(sub1)19 print(sub2)20 if len(sub1)%2:21 single1 = SingleNumber1(sub1)22 single2, single3 = SingleNumber3(sub2)23 else:24 single1 = SingleNumber1(sub2)25 single2, single3 = SingleNumber3(sub1)26 return single1, single2, single327 28 29 30 def func(Array):31 newArray = []32 for i in range(0,len(Array)):33 pos = 034 for j in range(0,32):35 if (Array[i]>>j) & 1:36 pos = j37 break38 newArray.append(1<<pos)39 return newArray
新聞熱點
疑難解答
