最近在微博上看到一道有趣的GOOGLE面試題肴颊，見(jiàn)下圖：
文字版：
一個(gè)大小為n的數(shù)組商叹，里面的數(shù)都屬于范圍[0, n-1]，有不確定的重復(fù)元素，
找到至少一個(gè)重復(fù)元素，要求O(1)空間和O(n)時(shí)間坟瓢。
這個(gè)題目要求用O(n)的時(shí)間復(fù)雜度，這意味著只能遍歷數(shù)組一次犹撒。同時(shí)還要尋找重復(fù)元素折联，很容易想到建立哈希表來(lái)完成，遍歷數(shù)組時(shí)將每個(gè)元素映射到哈希表中识颊，如果哈希表中已經(jīng)存在這個(gè)元素則說(shuō)明這就是個(gè)重復(fù)元素崭庸。因此直接使用C++ STL中的hash_set（參見(jiàn)《STL系列之六 set與hash_set》）可以方便的在O(n)時(shí)間內(nèi)完成對(duì)重復(fù)元素的查找。
但是題目卻在空間復(fù)雜度上有限制——要求為O(1)的空間谊囚。因此采用哈希表這種解法肯定在空間復(fù)雜度上是不符合要求的。但可以沿著哈希法的思路繼續(xù)思考执赡，題目中數(shù)組中所以數(shù)字都在范圍[0镰踏， n-1]，因此哈希表的大小為n即可沙合。因此我們實(shí)際要做的就是對(duì)n個(gè)范圍為0到n-1的數(shù)進(jìn)行哈希奠伪，而哈希表的大小剛好為n。對(duì)排序算法比較熟悉的同學(xué)不難發(fā)現(xiàn)這與一種經(jīng)典的排序算法——基數(shù)排序非常類(lèi)似。而基數(shù)排序的時(shí)間空間復(fù)雜度剛好符合題目要求绊率！因此嘗試使用基數(shù)排序來(lái)解這道面試題谨敛。
下面以2，4滤否，1脸狸，5，7藐俺，6炊甲，1，9欲芹，0卿啡，2這十個(gè)數(shù)為例，展示下如何用基數(shù)排序來(lái)查找重復(fù)元素菱父。
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 4 | 1 | 5 | 7 | 6 | 1 | 9 | 0 | 2 |
（1）由于第0個(gè)元素a[0] 等于2不為0颈娜，故交換a[0]與a[a[0]]即交換a[0]與a[2]得：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 1 | 4 | 2 | 5 | 7 | 6 | 1 | 9 | 0 | 2 |
（2）由于第0個(gè)元素a[0] 等于1不為0，故交換a[0]與a[a[0]]即交換a[0]與a[1]得：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 4 | 1 | 2 | 5 | 7 | 6 | 1 | 9 | 0 | 2 |
（3）由于第0個(gè)元素a[0] 等于4不為0浙宜，故交換a[0]與a[a[0]]即交換a[0]與a[4]得：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 7 | 1 | 2 | 5 | 4 | 6 | 1 | 9 | 0 | 2 |
（4）由于第0個(gè)元素a[0] 等于7不為0官辽，故交換a[0]與a[a[0]]即交換a[0]與a[7]得：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 9 | 1 | 2 | 5 | 4 | 6 | 1 | 7 | 0 | 2 |
（5）由于第0個(gè)元素a[0] 等于9不為0，故交換a[0]與a[a[0]]即交換a[0]與a[9]得：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 1 | 2 | 5 | 4 | 6 | 1 | 7 | 0 | 9 |
（6）由于第0個(gè)元素a[0] 等于2不為0梆奈，故交換a[0]與a[a[0]]即交換a[0]與a[2]野崇，但a[2]也為2與a[0]相等，因此我們就找到了一個(gè)重復(fù)的元素——2亩钟。
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 1 | 2 | 5 | 4 | 6 | 1 | 7 | 0 | 9 |
有了上面的分析乓梨，代碼不難寫(xiě)出：
//GOOGLE面試題
//一個(gè)大小為n的數(shù)組，里面的數(shù)都屬于范圍[0, n-1]清酥，有不確定的重復(fù)元素扶镀，找到至少一個(gè)重復(fù)元素，要求O(1)空間和O(n)時(shí)間焰轻。
#include <stdio.h>
const int NO_REPEAT_FLAG = -1;
void Swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}
//類(lèi)似于基數(shù)排序臭觉，找出數(shù)組中第一個(gè)重復(fù)元素。
int RadixSort(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
while (i != a[i])
{
if (a[i] == a[a[i]])
return a[i];
Swap(a[i], a[a[i]]);
}
}
return NO_REPEAT_FLAG;
}
void PrintfArray(int a[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
putchar('\n');
}
int main()
{
const int MAXN = 10;
int a[MAXN] = {2, 4, 1, 5, 7, 6, 1, 9, 0, 2};
//int a[MAXN] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
printf("數(shù)組為: \n");
PrintfArray(a, MAXN);
int nRepeatNumber = RadixSort(a, MAXN);
if (nRepeatNumber != NO_REPEAT_FLAG)
printf("該數(shù)組有重復(fù)元素辱志，此元素為%d\n", nRepeatNumber);
else
printf("該數(shù)組沒(méi)有重復(fù)元素\n");
return 0;
}
運(yùn)行結(jié)果如下圖所示：
整個(gè)程序的核心代碼只有短短5行左右蝠筑，雖然有二重循環(huán)語(yǔ)句，但每個(gè)元素只會(huì)被訪(fǎng)問(wèn)一次揩懒，完成符合題目對(duì)時(shí)間復(fù)雜度的要求什乙。
推薦閱讀：
經(jīng)典算法應(yīng)用之一----歸并排序（微軟筆試題）
經(jīng)典算法應(yīng)用之二----基數(shù)排序（google筆試題）
經(jīng)典算法應(yīng)用之三----應(yīng)用二中題目的升華
經(jīng)典算法應(yīng)用之四（上）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（中）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（下）---百度面試題
經(jīng)典算法應(yīng)用之五---隨機(jī)生成和為S的N個(gè)正整數(shù)
經(jīng)典算法應(yīng)用之六---過(guò)橋問(wèn)題和過(guò)河問(wèn)題
經(jīng)典算法應(yīng)用之七----10億數(shù)據(jù)中取最大的100個(gè)數(shù)據(jù)
