假設陣列具有1至1,000,000的整數。在具有整數的數組中，一個值在數組中有兩次。你如何確定哪一個？
我知道解決這個問題的一些常用方法：
我最近碰到另一種解決方案來了，我需要一些幫助，在瞭解背後邏輯它：
保持一個基數累加器。你異或 的索引和索引值都累加器。
x^C^x == C在這裏很有用，因爲每個數字將會是 的兩倍，除了那裏有兩次，這將出現3 次。 （x^x^x == x）和最終的索引，它會出現一次。 因此，如果我們用種子最終指數蓄電池，蓄電池的 終值將是在列表中的兩倍。
如果有人能幫助我理解這種方法背後的邏輯（用一個小例子！），我將不勝感激。
假設你有一個蓄電池
int accumulator = 0;
在你的循環的每一步，你XOR運算i和v，其中i是循環迭代的索引和v累加器在i個值陣列的位置。
accumulator ^= (i^v)
通常情況下，i和v將是相同的號碼，這樣你最終會做
accumulator ^= (i^i)
但i^i == 0，因此這將最終成爲一個空操作，累加器的值將保持不動。在這一點上，我應該說，數字的排列順序並不重要，因爲XOR是可交換的，所以即使陣列洗牌，並在最後的結果，開始應該還是0（累加器的初始值） 。
現在，如果陣列中出現兩次是多少？顯然，這個數字在XORing中會出現三次（一次是索引等於數字，一次是數字的正常外觀，另一次是額外的外觀）。此外，其他數字之一隻會出現一次（僅限其索引）。
此解決方案現在繼續假設僅出現一次的數字等於數組的最後一個索引，換句話說，數組中的數字範圍是連續的，並且從第一個索引開始處理（編輯：感謝CAF這個單挑評論，這是我腦子裏真的，但寫當我完全搞砸了）。有了這個（N只出現一次），作爲一個給定的，考慮開始
int accumulator = N;
有效地使N在異或再次出現兩次。在這一點上，我們剩下的號碼只出現兩次，而只有一個號碼出現三次。由於兩次出現的數字將異或爲0，所以累加器的最終值將等於出現三次（即一次額外）的數字。
邏輯是你只需要存儲累加器值，只需要經過一次數組。這很聰明。
當然，這是在實踐中的最佳方法取決於它有多少工作來計算異或，以及如何大的數組。如果數組中的值是隨機分佈的，那麼使用不同的方法可能會更快，即使它使用更多的內存，因爲在檢查整個數組之前很可能會發現重複值。
當然，如果數組是排序開始，事情是相當容易的。所以這很大程度上取決於數值在整個數組中的分佈情況。
1個10001包括顯示爲一個數組索引之間的每個數字。 （是不是C數組0索引？那麼，只要我們對數組值和索引都是從0開始還是從2開始都是一致的，它就沒有什麼區別。我將從數組開始1，因爲這是這個問題似乎是說什麼。）
無論如何，是的，1次10,001包出現，正是曾經之間的每一個數字，作爲數組的索引。每個介於1和10,000之間的數字也僅以數組值出現一次，除了出現兩次的重複值之外。所以數學上，我們正在做整體的計算如下：
1 xor 1 xor 2 xor 2 xor 3 xor 3 xor ... xor 10,000 xor 10,000 xor 10,001 xor D
，其中d是重複的值。當然，計算中的術語可能不會按順序出現，但xor是可交換的，所以我們可以重新排列我們喜歡的術語。對於每個n，n xor n爲0。所以上面簡化爲
10,001 xor D
xor this with 10,001 and you get D，the duplicated value。
感謝您的明確解釋！ – maxpayne
問題是：你有興趣知道如何做聰明但純粹學術異或技巧與現實世界沒有多大關聯，或者你想知道這一點，因爲在現實世界中，你可能會編寫使用數組的程序？這個答案解決了後一種情況。
無廢話的解決方案是要經過整個數組和你做排序。在排序時，確保沒有重複值，即實現抽象數據類型「set」。這可能需要分配第二個數組，並且排序很耗時。無論它是多少少費時比聰明的異或技巧，我不知道。
然而，有什麼好處ň未分類的值，你在現實世界中的數組？如果它們未排序，我們不得不假定它們的順序很重要，所以原始數組可能不得不保存。如果你想搜索原始數組或者分析它的重複數，中間值等等，你真的想要它的一個分類版本。一旦你有了它，你可以用「O log n」進行二進制搜索。
表示同意。但在面試中我被問到了這個問題，我想面試官對於沒有廢話的方法並不感興趣。 – maxpayne
從分析的角度來看，基數累加器方法在空間或時間方面更有效率嗎？我理解空間需求是O（1），時間複雜度是O（n）。但是，我認爲數組方法的總和具有相同的複雜度。對 ？ – brainydexter
沒有問題說整數是連續的，或者如果數組包含範圍內的所有數字。儘管對問題的簡要描述並未排除該數組，但基數解決方案似乎並不適用於{100,15,15,3,1000000}。 – Ross