數組中只出現一次的數字

題目：一個整型數組里，除了兩個數字以外，其他數字都出現了兩次，請寫程序找到這兩個只出現一次的數字。要求：時間復雜度為O(n),空間復雜度為O(1).

分析：看到這題，首先要明白，這是求兩個數字。還要明白其要求，空間復雜度和時間復雜度。如果沒有這些約束我們可以有很多方法解，如Hash、逐次遍歷等。

? ? ? ? 當常規方法無法滿足要求，我們就可以使用一個神奇的工具：位運算。

? ? ? ? 我們首先看看當只是一個數字是只出現一次怎么求解。

? ? ? ? 異或運算有一個性質：任何一個數字異或自己都等于0。多個數字依次做異或運算，相同的數字會抵消。看下例：

? ? ? ? 例如一個輸入數組：{1,2,3,2,3}

? ? ? ? 0001

? ? ? ? 0010 ?異或得到：

? ? ? ? 0011

? ? ? ? 0011 異或得到：

? ? ? ? 0000

? ? ? ? 0010 異或得到：

? ? ? ? 0010

? ? ? ? 0011 異或得到：

? ? ? ? 0001

? ? ? ? 看到木有，數組里面相同的數字都抵消了。這里只是針對只有一個數字是只出現一次的。其他情況不成立。

? ? ? ??

? ? ? ?但是本題里有兩個，直接這么做事不成立的，怎么辦？ 我們想到，用位整個數組運算以后得到的結果有什么作用呢？很明顯，出現兩次的數在位運算后抵消了，那么其實就是兩個只出現一次的兩個數做的位運算。例如：

? ? ? {1,2,2,3}

? ? ? 0001

? ? ? 0010 異或得到：

? ? ? 0011

? ? ? 0010 異或得到：

? ? ? 0001

? ? ? 0011 異或得到：

? ? ? 0010 ? ? ?這個結果和 ?1^3=0010是一樣了，驗證了上面的理論。

? ? ? 好了，有了這個有用的信息，那么我們就可以用這個結果中位為1來區分成兩組數據，很顯然這兩組數據中都分別只包含一個只出現一次的數字（作的異或運算嘛，=1，說明它們是不同的。）。然后再用最開始講到的方法去做就OK拉。代碼貼上來：

? ??

bool Judge(int pData, int BitIndex)
{pData = pData >> BitIndex;return (pData & 1);
}
void FindOnlyOneNumbers(int pData[],int length, int &num1,int &num2)
{//1.異常檢測if (pData == NULL || length < 2)return;//2.求出區分位int resultExclusive = 0;for (int i = 0; i < length; i++)resultExclusive ^= pData[i];      //假如只有一個數字是只出現一次，那么這個結果就是這個數字，如果兩個的話，那么這個數字中位為1即是只出現一次的兩個數的不同位。//3.接下來為了區分兩者，我們尋找區分位最右邊為1的位int indexCount = 0;while (resultExclusive&1==0&&indexCount<=8*sizeof(int)){resultExclusive >> 1;indexCount++;}//4.然后按照區分位的不同，將pData分成兩組,這里沒必要用兩個數組保存，直接進行用位運算分別計算兩個數就ok了int resultExclusive1 = 0, resultExclusive2 = 0;for (int i = 0; i < length; i++){if (Judge(pData[i],indexCount))resultExclusive1 ^= pData[i];elseresultExclusive2 ^= pData[i];}num1 = resultExclusive1;num2 = resultExclusive2;
}

?

? ? ? ??