查找數組中的重複元素

有一個大小爲n的數組，數組中包含的元素在1和n-1之間，這樣每個元素只出現一次，而只有一個元素出現多次。我們需要找到這個元素。查找數組中的重複元素

雖然這是一個非常常見的問題，但我仍然沒有找到正確答案。大多數建議是，我應該將數組中的所有元素相加，然後從中減去所有索引的總和，但如果元素的數量非常大，則這不起作用。它會溢出。還有一些關於使用異或門dup = dup^arr[i]^i的建議，這些我都不清楚。

我想出了這個算法，它是增加算法的一個增強，並且會在很大程度上減少溢出的機會！

for i=0 to n-1 
    begin : 
    diff = A[i] - i; 
    sum = sum + diff; 
    end

diff包含重複的元素，但使用這種方法，我無法找出重複的元素的索引。爲此，我需要再次遍歷數組，這是不可取的。任何人都可以想出一個更好的解決方案，不涉及加法方法或XOR方法在O（n）中工作嗎？

來源

2011-08-19 Poulami

這只是* [查找O（n）時間和O（1）空間中的重複項]（http://stackoverflow.com/q/5739024/134633）* – caf

中的問題的一個簡單情況。我需要再次遍歷數組，這是不可取的「爲什麼不可取？第二次遍歷數組不會改變算法的複雜性。 – sepp2k

@caf：那裏的解決方案修改了這裏看起來不太可取的數組。 –

根據問題描述的限制，您可以考慮很多方法來解決這個問題。

如果您知道一個事實，即只有一個元素重複，那麼有很多方法可以解決這個問題。一個特別聰明的解決方案是使用按位異或運算符。 XOR具有以下有趣的性質：

XOR是關聯的，所以（X^Y）^ Z = X ^（Y^Z）
XOR是可交換的：X^Y = Y^x的
XOR是其本身的逆：X^Y = 0當且僅當x = y
XOR具有零作爲同一性：X^0 = X

性能（1）和（2）在這裏的意思是服用時將一組值與XOR進行XOR，將XOR應用於元素的順序無關緊要。您可以對元素進行重新排序，或按照您認爲合適的方式進行分組屬性（3）意味着，如果你多次異或者相同的值，你會回到零，屬性（4）意味着如果你與0異或，你會得到你的原始數字。綜合所有這些屬性，您會得到一個有趣的結果：如果您採用一組數字的XOR，則結果是組中出現奇數次的所有數字的異或。原因是，當你將偶數次出現的數字異或時，可以將這些數字的異或分解爲一組對。每對通過（3）異或爲0，並且所有這些零的組合XOR通過（4）返回零。因此，所有甚至多樣性的數字都被抵消了。

要使用此解決原始問題，請執行以下操作。首先，將列表中的所有數字XOR在一起。這給出了出現奇數次的所有數的XOR，其結果是除了重複之外的從1到（n-1）的所有數字。現在，將該值與從1到（n-1）的所有數字的XOR異或。然後這會使先前未被取消的範圍爲1到（n-1）的所有數字抵消，只留下重複的值。此外，它運行在O（n）時間，並且僅使用O（1）空間，因爲所有值的XOR都適合一個整數。

在你原來的文章中，你考慮了一個替代方法，它使用從1到n-1的整數之和爲n（n-1）/ 2的事實。但是，您擔心這會導致整數溢出並導致問題。在大多數機器上，你是對的，這會導致溢出，但是（在大多數機器上）這不是問題，因爲算術是使用固定精度整數完成的，通常是32位整數。當發生整數溢出時，結果數字不是沒有意義的。相反，如果你計算出實際結果，它就是你得到的價值，然後放棄除最低32位之外的所有值。在數學上講，這被稱爲模算術，並且計算機中的操作是以模2進行的。更一般地說，儘管如此，假設對於一些固定的k，整數是以模k存儲的。

幸運的是，許多您熟悉並喜歡的算術法則仍然保留在模運算中。我們只需要用我們的術語更精確。我們說如果x和y除以k除以後的相同餘數，那麼x與y模k一致（表示爲x ≡ _k y）。在物理機器上工作時這很重要，因爲當大多數硬件發生整數溢出時，結果值與真值模k一致，其中k取決於字大小。幸運的是，下列法律持有真正的模塊化的算術：

例如：

如果x ≡ _ķ Y和W ≡ _ķ Z，那麼x + W ≡ _ķ Y + Z
如果x ≡ _ķ Y和W ≡ _ķ Z，然後XW ≡ _k yz。

這意味着如果要通過查找數組元素的總和並減去預期的總和來計算重複值，即使存在整數溢出，一切都會正常工作，因爲標準算術仍然會在硬件中產生相同的值（模k）。也就是說，你也可以使用基於異或的方法，它根本不需要考慮溢出。 :-)

如果你不能保證只有一個元素是重複的，但你可以修改元素數組，然後有一個美麗的算法來找到重複的值。 This earlier SO question描述如何完成這一點。直觀的想法是，您可以嘗試使用bucket sort對序列進行排序，其中元素數組本身也被循環使用以保存存儲區的空間。

如果您不能保證只有一個元素被複制，並且您不能修改元素數組，那麼問題就更加困難。這是一個經典的（而且很難！）面試問題，據報道，這個問題需要24小時解決。訣竅是將問題簡化爲cycle-finding的實例，方法是將數組作爲函數從數字1-n拖到1-（n-1）上，然後查找該函數的兩個輸入。然而，由此產生的算法，名爲，非常漂亮和簡單。有趣的是，在線性時間和恆定空間中，您將使用相同的算法來檢測鏈表中的週期。我建議您查看它，因爲它會定期進行軟件訪談。

對於具有分析性，正確性證明，以及Python實現算法沿的完整描述，請this implementation解決該問題。

希望這會有所幫助！

來源

2011-08-19 07:14:11 templatetypedef

一個有趣的註釋：xor是與這些屬性唯一的函數（達到同構）。換句話說，可數的無限組使得每個非同一元素都有二階是同構的。有秩序的有限羣體和每個非同一性元素的秩序2是同構的。 –

@ ChaoXu-你有參考我可以檢查一下嗎？另外，爲什麼不能證明無限數量的無限集？ – templatetypedef

對於有限情形，使用有限交換羣的基本定理，我們有全部有限羣，其中每個非同一元素的階2同構於（Z_2）^ n對於某個n，而Z_2中的+與xor相同。（這表明這些組的順序也必須是2^n）。對於可數無窮的情況，我寫了一個使用小組演示文稿的證明：http://chaoxuprime.com/2011/06/countably-infinite-group-such-that-every-element-has-order-2-are- isomorphic –

添加元素非常好，您只需在計算元素總數和期望總和時使用中間聚合的mod（％）即可。對於mod操作，你可以使用類似2n的東西。減法後您還必須修復這個值。

來源

2011-08-19 09:23:52

你能詳細說明一下嗎？我對這個解決方案並不熟悉，不能完全告訴你想要做什麼。你能發表更詳細的算法和正確性證明嗎？ – templatetypedef

這是一個在線算法。我使用OP描述的元素求和的總和，只是使用模算術，所以沒有溢出。你知道從1到n-1的數字總和。該數組包含n個數字，重複一個元素，所以只需取其總和，減去總和1-> n-1，然後得到重複的數字。 –

啊，錯過了「只有一個」的一部分，並認爲這是對更普遍的「一些元素重複」的情況。 – templatetypedef

查找數組中的重複元素

回答

相關問題