面試題:一個長度為n的數組，其中數組中每個元素的值都不大於n，如何用O(n)的演算法判斷數組中是否存在重複元素?

01-04

如題

既然沒有限定空間複雜度，那麼最簡單的辦法就是弄個HashSet或者另外弄一個長度為n的bool數組，然後一個個丟進去，時間複雜度確保在O(n)，而且一聽就明白，不需要思考和證明。

如果我是面試官，我會喜歡這種思維簡單粗暴直接的，因為需求沒說的東西都是不重要的東西。需求沒寫清楚是需求的問題，自己把問題搞複雜了，那是過度設計。

直覺告訴我，bool數組的性能應該優於交換元素。

var array = new bool[data.Length+1];


foreach( var i in data )

{

  if ( array[i] )

    return true;

  else

    array[i] = true;

}

return false;

這個題其實是在考察類似Union-Find問題，即順著數組編號尋找元素。用Lookup/HashSet的方法非常簡單直接，不過題目意圖應是要求O(1)空間完成。

思路是這樣：嘗試把每個數組元素t放到數組第t個位置上去（簡稱fix a[t]），若該位置數字已經為t，則出現重複，即不能fix，直接返回t。

藉助歸納法的思想：

- 當遍歷進行到j，j之前的所有位置皆已被fix；

- 處於第j個位置時，只要a[j]不為j，就嘗試把a[j]換到a[a[j]]去（即fix a[a[j]]），並循環該過程直到發現重複元素或者正確地fix a[j]；

- 繼續遍歷直到越界。

Python:

def find_repeated(a): j = 0 while j &< len(a): if a[j] == j: j += 1 else: while a[j] != j: if a[a[j]] == a[j]: # Number a[j] already there - duplicate number found. return a[j] else: # Can send number a[j] to its target position. # Swap the number there to here, and keep fixing. a[a[j]], a[j] = a[j], a[a[j]] # No duplicate number found. return None

雖然循環是兩層，但由於內層的每次交換對應一次fix，且每個位置不可能被fix第二次，故交換的次數必然小於n，符合O(n)時間和O(1)空間要求。

若元素非負，可以弄個長度為n+1的bool數組b[n+1]，初始全為false。記題中數組為num[]，迭代變數為i，

遍歷時可以:

if(b[num[i]]) return true;

b[num[i]]=true;

思路就是遍歷一遍數組，並將每個元素作為下標，即令b[num[i]]為true.當然，在賦值為true之前要先判斷是否已經為true了，若已經是true了說明有重複元素。

若元素有負數，可考慮用hashset

bool contain_duplicate(vector& arr){ for(int i=0;i&arr.size()){ continue; } if(i==cur-1) continue; if(arr[cur-1]==cur){ return true; } arr[i] = -1; while(1){ int next = arr[cur-1]; arr[cur-1] = cur; cur = next;

if(cur&<=0 || cur&>arr.size()){ break; } if(arr[cur-1]==cur){ return true; } } } return false; }

只判斷1-n的重複元素

O(n)-O(1)

1)不用全條件：O(n)-&>HashSet看有沒有碰撞 2):既然你說了不大於n(假設你說的是0-n),那麼initialize一個長度為n+1的boolean array,沒看到一個值就把那裡變成true,這種方法的好處是雖然他們的complexity一樣，但這個比HashSet 快scaler(如果是比賽的話不容易被大輸入timeout)

當題面描述說，長度為N的數組中裝的數字都不大於N，這已經是很明顯的暗示，要用數組值作為數組位置了。否則這倆N的聯繫就沒必要了。

如果是排列，而考慮到輪換的性質，只需要

循環 i=1..n

$$若a[i]≠0

$$j=i

$$repeat

$$$$if a[a[j]]=0

$$$$$$return 重複

$$$$j=a[k=j]

$$$$a[k]=0

$$until j=i

return 不重複

大概這樣就行了。。

如果說不使用額外空間。。。

為什麼不用位向量？省空間省時間啊

//arr是要判斷重複的數組，size數組長度。PS:以下代碼假設n小於32 //如果大於32可以把a定義成位長度為n的數組 int a[size/32 + 1] bool repeat(const int *arr, size_t size) { int a = 0; for(size_t i = 0; i &< size; i++) { if((a (1 &<&< arr[i])) == 0) { a += (1 &<&< arr[i]); } else { return true; } } return false; }

如果輸入不算O(n)之內的話，我認為可以再造一個數組查重即可。

#include &

int main(int argc, const char * argv[]) { int n; int a[1000], b[1000] = {0}; scanf("%d", n); for(int i = 0; i &< n; ++i) { scanf("%d", a[i]); } for(int j = 0; j &< n; ++j) { if(b[a[j]] == 0) { b[a[j]] = 1; } else { printf("FOUND! "); return 0; } } printf("NOT FOUND! "); return 0; }

上面的回答僅限小於n的自然數……

如果還有負數，考慮HashSet……

如果不是整數，我的姿勢水平可能就不行了=-=

there are two ways to solve the problem.

the first one is tricky. we use the high bits of every number as counters. for example, a[i] = x, it means that the number of number 「i」 is (x / n), at the same time the initial value of a[i] equals to (x % n). as i said, it"s quite tricky because if the length of the array is too large, it might lead to the mistake because of the overflow of the integers.

the time complexity is O(n), and only take O(1) extra memory space.

the second method is called #in-place radix sort# which take O(n) time and O(1) space. and it"s capable to deal with any arrays with variable length.

總體的思路就是數組A中的值(0 ~ n)作為B數組的下標，B數組的值用於存放A數組元素的計數值，判斷B數組的值是否大於1，大於1表明數組A的值有重複的。

int f(int A[]){

int B[n+1] = {0};

for(i=0; i& int j=0;

B[A[i]]++;

j = B[A[i]];

if (j &>1)

return 1

else

return0;

}

假如數組中存在負數，可以使用hashSet將其存進來就可以了

如果是正整數，求和，不等於1-n的和則有重複的

2^(num[0]-1) + 2^(num[1]-1) + …… + 2^(num[n-1]-1) == 2^n - 1

如果相等則無重複，不等則重複。

（原因很簡單，想想二進位。還不明白？編程珠璣第一章怎麼看的！）

最快最乾脆的方法當然是贊數最多的兄貴。

不過，既不佔用空間，代碼又少的應該跑不了了。

如果所有元素都大於0，也就是判斷數組中是否正好儲存了1..n，令i從1..n，假設a[i]==j,把a[i]與a[j]交換直到a[i]==i（沒問題，繼續檢查下個i）或者發現a[i]==a[j]（發現答案為否，終止）

如果所有元素的大小範圍已知且所有元素都是整數，而且允許額外佔用空間，可以開一個長為max-min的數組，其中max，min是所有元素的最大，最小可能取值。令i從1..n，利用那個數組檢查a[i]是否出現過就可以了。

如果可能出現實數，下界不明，不用額外空間我就不會了…允許額外空間可以用哈希判重，和上一個方法類似。

這兩天刷面試題正好刷到這題。我看到的要求是O(1)空間。方法就是基數排序。從數組的最開始loop，對於第i個元素，如果不是i，則交換a[i]和a[a[i]]，這樣每次交換使得某一個k，a[k]=k.一直交換到a[i]==i（增加i）或者發現a[i]==a[a[i]]（輸出結果），這樣就找到了重複元素。時間複雜度是O(n)因為我們每次操作都至少能使得一個k，a[k]=k，那麼遍歷整個array也最多需要n步，而在那之前，我們肯定已經發現重複的元素了。hashset是大家都會的，我還在網上看到了一些改成負的做標記，以及單鏈表循環的方法。就分享一種我覺得很簡單很清楚的。

算出1~n的異或和x，然後看這n個元素的異或和是不是x

就是簡單的計數hash吧

如果限定了數組中的數為正整數，用一個1..n的數組紀錄每個數出現的次數，遍歷一次看是否有超過二的

如果沒有上面的限定，不可能

根據題目，已經限定了時間複雜度為O(n)，而沒有限定空間複雜度，所以側重點實在考察有關時間複雜度的演算法。並且此題作為面試題，已經充分的給予了提示「其中數組中每一個元素的值都不大於n」,這句話就提示了，兩個n之前應該聯繫起來思考，既用數組值作為數組位置來思考。根據這樣的思考，則只需要設置諸如S[str[i]]這樣的數組作為解答判斷的關鍵就可以了。

詳細的，由於沒有強調空間複雜度，我們可以先設置一個空數組ch[]來存放判斷的flag，且為0，循環原本的str[]數組內部元素，如果存在了某一個str[i1]就將此時的ch[str[i1]]設為1，那麼如果再一次出現str[i2]這個數，此時判斷如果ch[str[i2]]==1,那麼就是重複了。（此時的str[i1]==str[i2],但是i是str[]從頭到尾遍歷的值，位置，所以i1!=i2）。

另外，Lintcode 有原題，原題鏈接：http://www.lintcode.com/zh-cn/problem/unique-characters/ ，大家如果感興趣，可以嘗試，按照上述方法，或者自己的方法寫一下再上傳，試試編程的結果是否正確，畢竟口說無憑。想直接要答案，亦可以直接查看參考答案：Unique Characters 參考答案，此答案提供了三種不同的思路，大家博取眾長，可以看看開拓眼界。

這是knuth大爺書上的

但是我以住在我客廳大哥@寇強的親身經驗告訴你，如果面試官問你，你還是回答 nlgn複雜度的演算法吧

大哥去年面fb，出了這題，他用n方法解答，面試官不懂，於是他用30分鐘教面試官如何做人，果然被拒了

你們猜面試官哪裡人？