查找給定數組中的兩個重複元素

給出一個n + 2元素的數組。數組的所有元素都在1到n的範圍內。除了出現兩次的兩個數字外，所有元素都會出現一次。找到兩個重複的號碼。查找給定數組中的兩個重複元素

例如，陣列= {4,2，4，5，2，3，1}和n = 5

專家我知道這個問題4個可能解決方案，但最近，我遇到對此我的溶液無法解釋。下面是解決方案

traverse the list for i= 1st to n+2 elements 
{ 
check for sign of A[abs(A[i])] ; 
if positive then 
    make it negative by A[abs(A[i])]=-A[abs(A[i])]; 
else // i.e., A[abs(A[i])] is negative 
    this element (ith element of list) is a repetition 
} 
Example: A[] = {1,1,2,3,2} 
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ; 
so list now is {-1,1,2,3,2} 

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition, 
now list is {-1,1,2,3,2} 

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated 
now list becomes {-1,-1,-2,3,2} 

i=4 ; 
and A[4]=3 is not repeated 

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition, 

This method modifies the original array.

的算法如何這個算法產生正確的結果，即它是如何working.Guys不要把這個作爲一個家庭作業的問題，因爲這問題已在最近被問微軟的採訪。

來源

2011-02-01 Algorithmist

@leppie這是另一個問題，因爲有兩個重複的號碼 – 2011-02-01 07:37:05

@belisarius：對不起:) Upvoted to counter'close'vote。 – leppie 2011-02-01 07:38:43

給你一個n + 2的數組元素。數組的所有元素都在1到n的範圍內。和所有元素除了這出現兩個數字發生一次兩次

讓我們稍微修改這一點，只有n，不n+2去，問題陳述的第一部分，它成爲

給你一個數組n 元素。該陣列的所有元素都在範圍1到n

所以，現在你知道你有一個數組，數組中的數字從1開始併爲數組中的每一個項目上去一個。所以如果你有10個項目，數組將包含1到10的數字。5個項目，你有1到5個等等。

接下來可以使用存儲在數組中的數字來索引數組。即你總是可以說A[A[i]]其中我< = A的大小。 A={5,3,4,1,2}; print A[A[2]]

現在，讓我們添加一個重複號碼。算法採用數組中每個數字的值，並訪問該索引。我們知道如果我們兩次訪問相同的索引，我們知道我們找到了重複。
我們如何知道我們是否兩次訪問相同的索引？是的，我們改變了我們訪問的每個索引中的數字的符號，如果符號已經改變，我們知道我們已經在這裏了，這個索引（不是存儲在索引處的值）是重複的數字。

您可以通過保留第二組布爾值來實現相同的結果，初始化爲false。這algroithm在MS問題變成

A={123412} 
B={false, false, false, false} 

for(i = 1; i <= 4; i++) 
{ 
    if(B[A[i]]) 
     // Duplicate 
    else 
     B[A[i]] = true; 
}

但是你改變的元素符號的一個，而不是設置一個布爾值B.

希望這有助於

來源

2011-02-01 07:51:55

你在做什麼是以兩種方式使用數組值：他們有一個數字，他們有一個標誌。你「存儲」了你在陣列中第n個位置看到n的事實，而不會丟失該位置的原始值：你只是在改變符號。

你從所有的肯定開始，如果你發現你的索引你想'保存'你已經看到你的當前值是已經是負數的事實，那麼這個值已經被看到了。

示例：因此，如果您第一次看到4，則將第四個點的符號更改爲負數。這不會改變第四點，因爲當你到那裏時你正在使用[abs]，所以不用擔心。如果你看到另外4個，你再次檢查第4個點，看它是否定的：presto：雙倍。

來源

2011-02-01 07:32:02 Nanne

當你在位置i找到某個元素，我們假設n，那麼你就會使A[abs(A(i))]=A[abs(n)]爲負數。所以如果你發現另一個包含n的位置j，你也將檢查A[abs(A(j))]=A[abs(n)]。既然你發現它是否定的，那麼n是重複的:)

來源

2011-02-01 07:39:58 zfm

簡單，使用一個Hashtable。

對於每個項目，檢查它是否已經存在O（1），如果沒有，將它添加到散列表O（1）。

當您找到一個已存在的項目...就是這樣。

來源

2011-02-01 17:28:01

我知道這並不是真的回答你的問題，但如果我真的必須在真實的項目上編寫這段代碼，我會從排序算法開始，比如quicksort，在我的比較函數中，比如

int Compare(int l, int r) 
{ 
    if(l == r) 
    { 
     // duplicate; insert into duplicateNumbers array if it doesn't exist already. 
     // if we found 2 dupes, quit the sort altogether 
    } 
    return r - l; 
}

我會將此歸入「性能和可維護性之間良好平衡」的可能解決方案。

來源

2011-02-01 17:43:29 tenfour

查找給定數組中的兩個重複元素

回答

相關問題