“一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字？”這是經(jīng)典的算法題，乍看這個(gè)題的思路特別多。
比如首先排序、然后在查找不同的數(shù)據(jù)就能找到這兩個(gè)數(shù)字，這種實(shí)現(xiàn)方法的時(shí)間復(fù)雜度應(yīng)該是在O(NlgN)，因?yàn)楸容^排序的算法最好的時(shí)間復(fù)雜度就是這樣。但是乍一看，這題就解決了，但是還沒(méi)有充分運(yùn)用一個(gè)條件，絕大多數(shù)元素是成對(duì)出現(xiàn)的，這個(gè)條件的作用是什么呢？ 當(dāng)然還有的思路就是hashmap實(shí)現(xiàn)，這種實(shí)現(xiàn)方法就是采用hash表存儲(chǔ)每個(gè)變量的次數(shù)，最后遍歷hash表即可，但是這種方法也存在問(wèn)題，如果存在負(fù)數(shù)，或者數(shù)組元素的值特別大，采用Hashmap實(shí)現(xiàn)的空間復(fù)雜度太大，并不是我們需要的解決方式，hashmap適合的方式是在一定范圍類(lèi)的數(shù)值進(jìn)行統(tǒng)計(jì)。上面這兩種方法可能是比較快速想到的。
這道題的實(shí)現(xiàn)方法很多，關(guān)鍵是找到最好的實(shí)現(xiàn)方法很難，本文就介紹采用異或運(yùn)算實(shí)現(xiàn)這道題目的解法。
異或運(yùn)算是C語(yǔ)言中位運(yùn)算的一種操作，這種操作對(duì)于嵌入式程序員可能比較熟悉，但是對(duì)于一般的程序員可能運(yùn)用的比較少，異或操作具有如下的特征：
0^num = num; 1^num = ~num; num ^ num = 0; 其中num = 0或者1。
運(yùn)用結(jié)合律等特征有：
a^a^b^b^c = (a^a)^(b^b)^c=0^0^c=c;
需要注意：如果有a + b = c; 則有可能使得a ^ b ^ c = 0;這個(gè)條件是非充分非必要，比如a = 1，b = 2， c = 3，這時(shí)候的a ^ b ^ c = 0是成立的，但是a = 2, b = 2, c = 4,則是不成立的。
從上面的結(jié)合律可以知道如果兩個(gè)相同的數(shù)進(jìn)行異或操作結(jié)果是0，根據(jù)題目中元素是成對(duì)出現(xiàn)的，可以充分運(yùn)用異或操作的結(jié)合特性，數(shù)組元素異或以后的結(jié)果肯定會(huì)包含兩個(gè)不成對(duì)元素的特征。
假設(shè)數(shù)組元素為a[N],其中N的值很大，不成對(duì)的元素為an,am。實(shí)現(xiàn)上述過(guò)程的步驟如下所示：
首先，變量元素對(duì)所有元素進(jìn)行異或操作，得到的結(jié)果肯定是an^am。也就說(shuō)通過(guò)異或操作以后，結(jié)果中保存了an和am的特征。由于am和an不同，am^an的結(jié)果肯定是大于等于1。am和an不同，那么am^an中為1的某一個(gè)bit肯定是am或者an中某一個(gè)的特征。
然后，定義兩個(gè)值num1，num2，分別用來(lái)計(jì)算an、am，選擇am^an中的某一個(gè)bit作為特征位，假設(shè)是第K位是特征位，再次對(duì)元素進(jìn)行遍歷，如果元素的第K位是1，這個(gè)元素可能是am或者an，那么將當(dāng)前元素與num1進(jìn)行異或操作，如果元素的第K為不為0，那么這個(gè)元素則可能是另一個(gè)值，那么將當(dāng)前元素與num2進(jìn)行異或操作。這樣遍歷完所有元素，因?yàn)榇蟛糠謹(jǐn)?shù)據(jù)成對(duì)出現(xiàn)，根據(jù)異或運(yùn)算的特征，num1，num2就分別保存了兩個(gè)不同的值。
由上面的分析可知，這種算法只需要遍歷兩次數(shù)組空間即可實(shí)現(xiàn)數(shù)據(jù)的判定，這樣時(shí)間復(fù)雜度為O(N),同時(shí)因?yàn)闆](méi)有hashmap之類(lèi)的結(jié)構(gòu)體，這樣空間復(fù)雜度就是O(1)。這種算法的實(shí)現(xiàn)肯定是最佳的。相比前面提到的hashmap、排序算法時(shí)間復(fù)雜度和空間復(fù)雜度都要小，因此這種算法的實(shí)現(xiàn)應(yīng)該是最佳的。
代碼實(shí)現(xiàn)如下：
#include<stdio.h>
#include<stdlib.h>
int whichbitone(int in)
{
int i = 0;
while((in & (1 << i)) == 0)
i ++ ;
return i;
}
int isbitone(int in, int k)
{
if((in & (1 << k)) != 0)
return 1;
else
return 0;
}
void xortest(int *array, int size)
{
int dxor = 0, xor = 0;
int i = 0, j = 0;
int num1 = 0, num2 = 0;
for(i = 0; i < size; ++ i)
dxor ^= array[i];
if(dxor != 0)
{
j = whichbitone(dxor);
for(i = 0; i < size; ++ i)
{
if(isbitone(array[i],j) == 1)
num1 ^= array[i];
else
num2 ^= array[i];
}
/*得到第一個(gè)數(shù)*/
printf("first data is %d\n",num1);
printf("second data is %d\n",num2);
}
}
int main(int argc, char *argv[])
{
int array[10] = {1,2,3,4,7,2,3,1,4,9};
xortest(array,10);
return 0;
}
上面的代碼基本上實(shí)現(xiàn)了上面的描述。
對(duì)于本題的另一個(gè)變換“數(shù)組中元素成對(duì)出現(xiàn)，但是存在三個(gè)不成對(duì)的元素，如何快速的找出這三個(gè)元素？”
這個(gè)題看起來(lái)和本題有一定的聯(lián)系性，甚至我認(rèn)為我們可以采用相同的方法找出三個(gè)值，但是后來(lái)發(fā)現(xiàn)這種方法存在一個(gè)問(wèn)題，但是三個(gè)的情況要遠(yuǎn)遠(yuǎn)比兩個(gè)的復(fù)雜，因?yàn)槠渲写嬖诘目赡苄砸嗪芏啵皇遣皇菍儆谶@個(gè)元素就是另一個(gè)元素的問(wèn)題，雖然這種解法可能導(dǎo)致問(wèn)題產(chǎn)生，但是還是有可能解決的，除了當(dāng)三個(gè)元素的異或結(jié)果為0，即x^y^z = 0時(shí)，這種方法是不成立的。
對(duì)于三個(gè)不同元素的找份，我認(rèn)為主要是找到其中的一個(gè)元素，然后將這個(gè)元素移除，在進(jìn)行上述的另外兩個(gè)元素尋找。當(dāng)然我們首先排除三個(gè)數(shù)據(jù)異或?yàn)榱愕奶厥馇闆r。具體的實(shí)現(xiàn)可以參考http://blog.csdn.net/zzran/article/details/8108787。
還是存在這個(gè)問(wèn)題，如果這三個(gè)元素異或以后的值剛好為零，這種方法不能解決了，因此采用異或解決只有一個(gè)不成對(duì)或者兩個(gè)不同元素的問(wèn)題是沒(méi)有問(wèn)題的，對(duì)于三個(gè)元素具有一定的可行性，但是不一定時(shí)時(shí)成立。
異或運(yùn)算在算法中針對(duì)的問(wèn)題也是特定的，主要是這種元素成對(duì)出現(xiàn)的問(wèn)題，如果不成對(duì)出現(xiàn)，這種算法的實(shí)用性能會(huì)大大的降低，即使是重復(fù)元素都不一定是實(shí)用的。