首先來看題目要求：
在一個(gè)數(shù)組中除兩個(gè)數(shù)字只出現(xiàn)1次外歼培，其它數(shù)字都出現(xiàn)了2次檩淋， 要求盡快找出這兩個(gè)數(shù)字漾稀。
考慮下這個(gè)題目的簡(jiǎn)化版——數(shù)組中除一個(gè)數(shù)字只出現(xiàn)1次外抵代，其它數(shù)字都成對(duì)出現(xiàn)腾节，要求盡快找出這個(gè)數(shù)字。這個(gè)題目在之前的《經(jīng)典排序算法應(yīng)用之4（中）---基本位操作之算法篇
》中的“位操作趣味應(yīng)用”中就已經(jīng)給出解答了。根據(jù)異或運(yùn)算的特點(diǎn)案腺，直接異或一次就可以找出這個(gè)數(shù)字庆冕。
現(xiàn)在數(shù)組中有兩個(gè)數(shù)字只出現(xiàn)1次，直接異或一次只能得到這兩個(gè)數(shù)字的異或結(jié)果劈榨，但光從這個(gè)結(jié)果肯定無法得到這個(gè)兩個(gè)數(shù)字访递。因此我們來分析下簡(jiǎn)化版中“異或”解法的關(guān)鍵點(diǎn)，這個(gè)關(guān)鍵點(diǎn)也相當(dāng)明顯——數(shù)組只能有一個(gè)數(shù)字出現(xiàn)1次同辣。
設(shè)題目中這兩個(gè)只出現(xiàn)1次的數(shù)字分別為A和B拷姿，如果能將A，B分開到二個(gè)數(shù)組中旱函，那顯然符合“異或”解法的關(guān)鍵點(diǎn)了响巢。因此這個(gè)題目的關(guān)鍵點(diǎn)就是將A，B分開到二個(gè)數(shù)組中棒妨。由于A踪古，B肯定是不相等的，因此在二進(jìn)制上必定有一位是不同的靶衍。根據(jù)這一位是0還是1可以將A灾炭，B分開到A組和B組。而這個(gè)數(shù)組中其它數(shù)字要么就屬于A組颅眶，要么就屬于B組蜈出。再對(duì)A組和B組分別執(zhí)行“異或”解法就可以得到A，B了涛酗。而要判斷A铡原，B在哪一位上不相同，只要根據(jù)A異或B的結(jié)果就可以知道了商叹，這個(gè)結(jié)果在二進(jìn)制上為1的位都說明A燕刻，B在這一位上是不相同的。
比如int a[] = {1, 1, 3, 5, 2, 2}
整個(gè)數(shù)組異或的結(jié)果為3^5即 0x0011 ^ 0x0101 = 0x0110
對(duì)0x0110剖笙，第1位（由低向高卵洗，從0開始）就是1。因此整個(gè)數(shù)組根據(jù)第1位是0還是1分成兩組弥咪。
a[0] =1 0x0001 第一組
a[1] =1 0x0001 第一組
a[2] =3 0x0011 第二組
a[3] =5 0x0101 第一組
a[4] =2 0x0010 第二組
a[5] =2 0x0010 第二組
第一組有{1, 1, 5}过蹂，第二組有{3, 2, 3}，明顯對(duì)這二組分別執(zhí)行“異或”解法就可以得到5和3了聚至。
分析至些酷勺，相信代碼不難寫出，下面給出完整的源代碼：
// 百度面試題
//數(shù)組中除兩個(gè)數(shù)字外扳躬，其它數(shù)字都出現(xiàn)了次脆诉。要求盡可能快的找出這兩個(gè)數(shù)字
void FindTwoNotRepeatNumberInArray(int *a, int n, int *pN1, int *pN2)
{
int i, j, temp;
//計(jì)算這兩個(gè)數(shù)的異或結(jié)果
temp = 0;
for (i = 0; i < n; i++)
temp ^= a[i];
// 找第一個(gè)為1的位
for (j = 0; j < sizeof(int) * 8; j++)
if (((temp >> j) & 1) == 1)
break;
// 第j位為1,說明這兩個(gè)數(shù)字在第j位上是不相同的
// 由此分組即可
*pN1 = 0, *pN2 = 0;
for (i = 0; i < n; i++)
if (((a[i] >> j) & 1) == 0)
*pN1 ^= a[i];
else
*pN2 ^= a[i];
}
void PrintfArray(int a[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
putchar('\n');
}
int main()
{
const int MAXN = 10;
//int a[MAXN] = {1, 2, 7, 5, 100, 100, 6, 1, 2, 5};
int a[MAXN] = {1, 2, 3, 4, 1, 2, 3, 4, 0, 5};
printf("數(shù)組為: \n");
PrintfArray(a, MAXN);
int nNotRepeatNumber1, nNotRepeatNumber2;
FindTwoNotRepeatNumberInArray(a, MAXN, &nNotRepeatNumber1, &nNotRepeatNumber2);
printf("兩個(gè)不重復(fù)的數(shù)字分別為: %d %d\n", nNotRepeatNumber1, nNotRepeatNumber2);
return 0;
}
運(yùn)行結(jié)果如下所示：
推薦閱讀：
經(jīng)典算法應(yīng)用之一----歸并排序（微軟筆試題）
經(jīng)典算法應(yīng)用之二----基數(shù)排序（google筆試題）
經(jīng)典算法應(yīng)用之三----應(yīng)用二中題目的升華
經(jīng)典算法應(yīng)用之四（上）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（中）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（下）---百度面試題
經(jīng)典算法應(yīng)用之五---隨機(jī)生成和為S的N個(gè)正整數(shù)
經(jīng)典算法應(yīng)用之六---過橋問題和過河問題
經(jīng)典算法應(yīng)用之七----10億數(shù)據(jù)中取最大的100個(gè)數(shù)據(jù)
