算法：在數組中查找單個數字

Question

這是我剛纔看到的一個leetcode問題。有人給出的解決方案有點難以理解，我希望有人可以詳細說明一下：

給定一個整數數組，每個元素出現三次，除了一次，只出現一次，只出現一次。找到那一個。

這樣做是在線性時間內沒有額外的空間。

解決方案有人給：

public int singleNumber(int[] A) { 
    int ones = 0, twos = 0; 
    for(int i = 0; i < A.length; i++){ 
     ones = (ones^A[i]) & ~twos; 
     twos = (twos^A[i]) & ~ones; 
    } 
    return ones; 
} 

這似乎是一個真棒的解決方案，但它是一個有點難以理解。評論中有人表示這可以擴展到任何數量的重複。

Answer 1

假設對於int中的每個位，都有一個計數器。該計數器可以取值0,1或2.對於輸入數字中的每個1位，您將增加相應的計數器，當您按3時循環返回到0.

如果一個數字出現3次數組中，對應於其1位的計數器將爲該數字增加3次，最終不起作用。一次出現的數字將使其相應的計數器遞增一次，因此最後計數器將只反映出現一次的數字的1位。

這基本上是一個三元版本的「XOR所有」解決方案，如果重複的數字出現2次而不是3次，我們可以進一步使用三元數據，並使用輸入的基數3位數來代替的位，但位更容易處理。

---

的ones和twos變量用於保持這些計數器。 ones變量中的1位對應於計數器值1，並且twos變量中的1位對應於計數器值2.計數器值0對應於ones和twos中的0位。

此：

ones = (ones^A[i]) & ~twos; 
twos = (twos^A[i]) & ~ones; 

是一個計數器更新。在一點一點的基礎上看看它。

如果A[i]中的某位設置爲0，則這些行不會影響ones和twos中的該位。

如果一個位被設置爲1 A[i]，然後

• 如果該位被ones設置，這是取消所有在ones（因爲^ A[i]的），並在twos（設置，因爲^ A[i]，並那麼& ~ones不會取消它，因爲我們只是取消了ones中的位）。
• 如果該位被twos設置，它保持在ones取消設置（因爲& ~twos的），並在twos得到取消設置（因爲^ A[i]的）。
• 如果該位在兩個ones和twos被清除的，它得到ones設置（因爲^ A[i]的），並在twos仍然未設置（因爲& ~ones的）。

最後，ones有其位對應的A只出現過一次的元素集合，讓我們回到ones。

Answer 2

這只是將所有元素異或。不需要任何額外的結構或容器，運行時將由容器的遍歷時間定義，O(n)用於數組遍歷。 XOR二元運算符的真值表說，如果被比較的兩個元素不相等，它將只產生非零的東西。

所以，如果您有任何N號碼其中重複k次爲k > 2，這種方法會發現它不具有多重k > 2（這意味着它必須是K = 1，數組的元素寂寞）的單個元素。我可能會誤解，但我相信這個解決方案已經適用於所有重複多> 2.