技術(shù)群里有人提出一個(gè)算法題：一個(gè)Int型數(shù)組瓶逃，里面的每一個(gè)數(shù)都是成雙成對的束铭，只有一個(gè)數(shù)是單身狗，找出這個(gè)數(shù)厢绝，算法復(fù)雜度<= O(n)
思路很簡單契沫，通過異或運(yùn)算就可以找到這個(gè)數(shù)。
下面昔汉，升級版的算法題來了懈万。
一個(gè)Int型數(shù)組，里面的每一個(gè)數(shù)都是成雙成對的靶病，只有兩個(gè)可憐的單身狗会通，找出這個(gè)兩個(gè)數(shù)，時(shí)間復(fù)雜度<= O(n)娄周，空間復(fù)雜度 O(1)涕侈？
答案見下方。
·
·
·
·
·
·
·
我
是
分
割
線
·
·
·
·
·
·
·
·
·
·
·
·
bool FindDog() {
int a=0;
int b=0;
const int length = 12;
int arr[length] = {1,2,3,4,5,6,810,5,4,3,2,1};
int aXORb =0;
for (int i=0; i<length; i++) {
aXORb ^= arr[i];
}
//查找兩個(gè)單身狗的異或值煤辨，如果為0裳涛，則說明不存在兩條單身狗木张。
if( 0 == aXORb){
printf("數(shù)據(jù)錯(cuò)誤\n");
return false;
}
//假設(shè)異或值為 0010100，則提取出 0000100
int mask = 0x0;
int flag = 0;
while (flag < sizeof(int)) {
mask = 0x1 << flag;
int AB = aXORb & mask;
if (AB>0) {
break;
} else {
flag++;
}
}
if( 0 == mask){
printf("數(shù)據(jù)錯(cuò)誤\n");
return false;
}
//假設(shè)掩碼為 0000100调违，則兩個(gè)結(jié)果的右數(shù)第3不一致。
//通過它泻轰，我們拆分?jǐn)?shù)組為分別包含兩個(gè)結(jié)果的數(shù)組（相同的數(shù)必定在同一數(shù)組技肩，兩個(gè)結(jié)果必定在不同數(shù)組），并分別求值
for (int i=0; i<length; i++) {
if (arr[i] & mask) {
a ^= arr[i];
}else{
b ^= arr[i];
}
}
printf("?? = %d \n",a);
printf("?? = %d \n",b);
return true;
}
