題目：一個(gè)整型數(shù)組里除了3個(gè)數(shù)字之外疯溺，其他的數(shù)字都出現(xiàn)了兩次弹澎。請寫程序找出這3個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n)很泊，空間復(fù)雜度是O(1)角虫。
這道利用異或的經(jīng)典面試題目出現(xiàn)很久了，我倒也參考過不少資料委造，但大部分講得都比較費(fèi)解〈炼欤現(xiàn)在我用大白話來解釋一下思路。
1.直接求解該題比較麻煩昏兆，不妨先將題目簡化枫虏，如果只有一個(gè)數(shù)字是單獨(dú)出現(xiàn)的，那么我們可以很快想到將數(shù)組的所有數(shù)字異或一遍爬虱，得到的結(jié)果就是單獨(dú)的那個(gè)數(shù)字：
代碼很快可以寫出來：
void findOne(int arr[],unsigned int len){
if(arr==NULL || len<1)return;
int i,result = 0;
for (i = 0; i < len; i++){
result ^= arr[i];
}
printf("result = %d \n",result);
}
2.如果是兩個(gè)數(shù)字設(shè)為a,b單獨(dú)出現(xiàn)模软，直接全部異或得到的結(jié)果c是a^b的結(jié)果，即 c = a^b ;好像求不出a,b饮潦，但是咋們不妨先回憶一下異或的運(yùn)算規(guī)則：
^ 0 1
0 0 1
1 1 0
由于a ≠ b 所以 c ≠ 0，所以c的二進(jìn)制位一定不全為0携狭，假設(shè)二進(jìn)制位最后一位1出現(xiàn)的位置為 m ，那么對m位而言 a與b的異或結(jié)果為 1，顯然a與b在該位不同麦牺，
eg: a = 2,b=12,c=a^b;
a:0000 0000 0000 0000 0000 0000 0000 0010
b:0000 0000 0000 0000 0000 0000 0000 1100
c:0000 0000 0000 0000 0000 0000 0000 1110
c最后一個(gè)1出現(xiàn)的位置為 倒數(shù)第2位蝴蜓，在這一位上a為1，b為0
據(jù)此可以區(qū)分出a與b单默，不妨假設(shè)a的m位為1碘举，那么在數(shù)組所有第m位為1的數(shù)字中，只有a一個(gè)數(shù)字是單獨(dú)出現(xiàn)（其余成對的數(shù)字如果在m位為1搁廓，那也是成對出現(xiàn)的）引颈！
至此耕皮，該問題可以簡化為問題 1的情況，找到a后蝙场，根據(jù)公式： aba = (aa)b = 0^b = b 就可以得到b即： b = c^a;
代碼如下：
//只保留num的最后一位的1 其余位為置0
int lastBitOf1(int num){
return num & ~(num - 1);
}
void findTwo(int arr[],int len){
if(arr==NULL || len<1) return;
int i,a=0,b=0,c=0;
for (i = 0; i < len; i++){
c ^= arr[i];
}
int lastZero = lastBitOf1(c);
for (i = 0; i < len; i++){
if( arr[i] & lastZero )
a ^= arr[i];
}
b = c^a;
printf("a=%d \n",a);
printf("b=%d \n",b);
}
3.如果是3個(gè)數(shù)字設(shè)為a,b,c單獨(dú)出現(xiàn)的情況
看到這里凌停，想必我們自然而然會想到如何找到這三個(gè)數(shù)字中的區(qū)別，據(jù)此找到一個(gè)數(shù)字售滤，然后該問題即可轉(zhuǎn)化為找2個(gè)單獨(dú)出現(xiàn)的數(shù)字的問題了罚拟。
現(xiàn)在如果也將數(shù)組所有數(shù)字相互異或，那么得到的將是a,b,c的異或結(jié)果完箩，不妨設(shè)為 x,即 x = abc赐俗，由于a,b,c各不相同則 x ≠ 0
而且有 x^a ≠ 0; x^b ≠ 0 ; x^c ≠ 0
證明如下: 如果 x^a = 0，即 (a^b^c)^a = b^c = 0 則 b == c,與題目矛盾弊知，同理可證明 x^b ≠ 0 ; x^c ≠ 0
那么 lastBitOf1(x^a) lastBitOf1(x^b) lastBitOf1(x^c) 都不為0阻逮，為了方便起見，不妨令 fun(n) = lastBitOf1(n); 即 fun(xa)fun(xb)fun(x^c) ≠ 0
不妨令 N = fun(x^a) ^ fun(x^b) ^ fun(x^c), 假設(shè)N的最后一位1出現(xiàn)的位置為 pos,
fun(x^a) fun(x^b) fun(x^c) N
0 0 0 0
1 0 0 1
1 1 0 0
1 1 1 1
在第pos位上 fun(xa),fun(xb),fun(x^c) 中有1個(gè)或者3個(gè)為 1吉捶。
假設(shè)3個(gè)都為1夺鲜，那么在第pos位 a,b,c都相同且與x不同，
如果在第pos位a,b,c都是0的話 x 在該位的結(jié)果為 000 = 0 與假設(shè)矛盾
如果在第pos位a,b,c都是1的話 x 在該位的結(jié)果為 111 = 1 與假設(shè)矛盾
故第pos位上 fun(xa),fun(xb),fun(x^c) 中只有1個(gè)1,不妨令 fun(x^a) 在pos位為1 終于找到a,b,c的區(qū)別了呐舔。
至此币励，我們可以將這個(gè)問題轉(zhuǎn)化為：
數(shù)組所有與x的異或的結(jié)果的最后一位1出現(xiàn)在pos位的數(shù)中只有一位是單獨(dú)出現(xiàn)的，其余成對出現(xiàn)
這句話有點(diǎn)繞珊拼，不妨表達(dá)如下
所有滿足 fun(arr[i]^x) 的最后一位1出現(xiàn)在第pos位的數(shù)中食呻，只有a是單獨(dú)出現(xiàn)的，其余成對出現(xiàn)
x為數(shù)組所有數(shù)相互異或的結(jié)果 即 x = arr[0]arr[1]...^arr[n-1];
根據(jù)問題1的求解我們可以很容易求出a,偽代碼如下:
int a= 0;
int i;
for(i=0;i<len;i++){
if(arr[i]^x的最后一位1的位置為pos){
a ^= arr[i];
}
}
再根據(jù)問題2的求解我們就可以求出其余的兩個(gè)數(shù)b,c了 澎现。代碼如下：
void getThreeUnique(int numbers[], unsigned int len){
if(numbers == NULL || len<1)return;
//輔助數(shù)組仅胞，找到一個(gè)數(shù)后，將它放到numbers中剑辫，即可轉(zhuǎn)化為findTwo求解
int temp [len+1];
//數(shù)組所有數(shù)字的異或結(jié)果
int xorResult = 0;
int i,flags = 0;
for (i = 0; i < len; i++){
xorResult ^= numbers[i];
temp[i] = numbers[i];
}
for (i = 0; i < len; i++){
flags ^= lastBitOf1(xorResult ^ numbers[i] );
}
// flags為 f(x^a)^f(x^b)^f(x^c)的結(jié)果
flags = lastBitOf1(flags);//保留flags最后一位1
int first = 0,second = 0,third = 0;
for (i = 0; i < len; i++){
// x^a,x^c,x^c中 只有1個(gè)第m位為1
if( lastBitOf1(numbers[i] ^ xorResult) == flags)
first ^= numbers[i];
}
//找到一個(gè)數(shù)字后干旧，將它放到原來的數(shù)組中，轉(zhuǎn)化為 findTwo 的問題
temp[len] = first;
xorResult ^= first;
flags = lastBitOf1(xorResult);
for (i = 0; i < len+1; i++){
if( temp[i] & flags )
second ^= temp[i];
}
third = xorResult^second;
printf("%d,%d,%d \n",first,second,third);
}
