九、一道有趣的GOOGLE面试题

---

 

---

问题的数学性描述:

一个大小为n的数组，里面的数都属于范围[0,
n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。

哈希表可以在遍历数组一次的情况下找到重复元素，时间复杂度也为O（n）,但是空间复杂度不能降为O（1），所以不适合这道题

而基数排序的时间和空间复杂度刚好符合题目要求

1.基数排序查找重复元素示例

下面以2，4，1，5，7，6，1，9，0，2这十个数为例，展示下如何用基数排序来查找重复元素。

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 2 4 1 5 7 6 1 9 0 2

---

（1）由于第0个元素a[0]
等于2不为0，故交换a[0]与a[a[0]]即交换a[0]与a[2]得：

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 1 4 2 5 7 6 1 9 0 2

---

（2）由于第0个元素a[0]
等于1不为0，故交换a[0]与a[a[0]]即交换a[0]与a[1]得：

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 4 1 2 5 7 6 1 9 0 2

---

（3）由于第0个元素a[0]
等于4不为0，故交换a[0]与a[a[0]]即交换a[0]与a[4]得：

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 7 1 2 5 4 6 1 9 0 2

---

（4）由于第0个元素a[0]
等于7不为0，故交换a[0]与a[a[0]]即交换a[0]与a[7]得：

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 9 1 2 5 4 6 1 7 0 2

---

（5）由于第0个元素a[0]
等于9不为0，故交换a[0]与a[a[0]]即交换a[0]与a[9]得：

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 2 1 2 5 4 6 1 7 0 9

---

（6）由于第0个元素a[0]
等于2不为0，故交换a[0]与a[a[0]]即交换a[0]与a[2]，但a[2]也为2与a[0]相等，因此我们就找到了一个重复的元素——2。

---

下标 0 1 2 3 4 5 6 7 8 9

---

数据 2 1 2 5 4 6 1 7 0 9

---

Pasted from:
<[http://blog.csdn.net/morewindows/article/details/8204460]{.ul}>

2.算法

Radixsort方法，这个方法满足要求，但是只能查找到一个重复元素

1. int Radixsort(int a[], int n)

2. {

3. int i;

4. for (i = 0; i < n; i++)

5. {

6. while (i != a[i])

7. {

8. if (a[i] == a[a[i]])

9. return a[i];

10. Swap(&a[i], &a[a[i]]);

11. }

12. }

13. return NO_REPEAT_FLAG;

14. }

FindRepeatNumberInArray方法，标记查到的数，再次查到就说明作为索引的数重复了

1. int FindRepeatNumberInArray(int * a, int n)

2. {

3. for (int i = 0; i < n; i++)

4. {

5. //每查到一个数就加n作为标记，如果后面的数的值有一个再查到了这个数，这个时候这个数是大于n的，就说明这个值跟之前某个数重复

6. int nRepeatIndex = a[i] >= n ? a[i] - n : a[i];

7. if (a[nRepeatIndex] >= n)

8. return nRepeatIndex;

9. else

10. a[nRepeatIndex] += n;

11. traverse(a, n);

12. }

13. return NO_REPEAT_FLAG;

14. }