數組中有4*k+2個整數，其中k個整數出現4次，1個整數出現2次。找出出現2次的那個整數？時間和空間越小越好

01-09

可以通過排序找到這個數。但是時間複雜度有點高啊。有什麼更好的方法嗎？

接著樓上的答案，一個更高效的實現是用位運算構造一個狀態機。假設輸入是一個整型的數組P[i]，總共4個狀態我們需要用2個整型來表示。構造狀態機如下：

00 -&> 01 -&> 10 -&> 11

然後湊一下，第一個數是否變化取決於第二個數，第二個數總是要變。所以代碼如下：

int A = 0, B = 0; for (int i = 0; i &< 4 * K + 2; i++) { A ^= P[i] B; B ^= P[i]; }

如果輸入數據無誤，那麼B一定等於0，A就是所求的那個數

讓我們簡化一下這個問題：

有 2k+1 個整數，除一個以外均恰好出現兩次。

經典做法是，將此 2k+1 個整數全部異或（xor）起來。由於 xor 的性質：

A xor A = 0, A xor B = B xor A, A xor 0 = A，易證明最終結果就是只出現一次的那個數。

回到原問題，我們需要構造一種「四數相消」的異或運算。

異或的本質其實是，對於每一個二進位位進行模 2 加法運算。

所以此問題只需要改模 2 為模 4 即可（最後將結果除以 2）。

例：

[3, 5, 2, 5, 3, 2, 5, 5, 3, 3]

二進位位：

011

101

010

101

011

010

101

011

模 4 加法：

020

每位除 2，化為十進位：

010 =&> 2

時間複雜度 O(n * 位數)，額外空間 O(1)。

給 @Vichare Wang 的答案做個註解。

其方法可概括為：

將數組 P[i] 中每個整數的對應bit做 i 上的累加，於是就得到每個bit上 1 出現的次數，

再將結果 mod 4，會有 00,01,10,11，4種餘數的結果，為每一種分配狀態。

根據題目約束，

每個bit上1要麼出現4的整數倍次，最終狀態餘數為 00 ，（可推斷出現兩次的數在該bit上=0）

要麼還多出2次，最終狀態餘數為 10，（表示出現兩次的數在該bit上=1）

用AB來表示這個狀態，計算過程是不斷的對B做二進位加法（異或），進位到A：

$State[j]=A.bit[j]B.bit[j]=(sum_{i=0}^{2K+2}{P[i].bit[j]} )mod4$

這個經典：

結果是 $left( sum_{i=1}^{4k+2}{P[i]} ight)$ %4 $div$ 2

可以用快速劃分來做。

如果左邊的元素數NL % 4 == 2，則繼續在左邊找答案。

如果右邊的元素數NR % 4 == 2, 則在右邊找答案。

時間複雜度O(N)，空間複雜度O(1)。不需要考慮正負數。