[经典面试题][谷歌]一个大小为n的数组，里面的数都属于范围[0, n

题目

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

思路一

寻找重复元素，很容易想到建立哈希表来完成，遍历一遍数组就可以将每个元素映射到哈希表中。如果哈希表中已经存在这个元素则说明这就是个重复元素。这种方法可以很方便的在O(n)时间内完成对重复元素的查找。可是题目要求在O(1)的空间。因此采用哈希表这种解法肯定在空间复杂度上是不符合要求的。题目中数组中所以数字都在[0, n-1]区间范围内，因此哈希表的大小为n。因此我们实际要做的就是对n个范围为0到n-1的数进行哈希，而哈希表的大小刚好为n。对排序算法比较熟悉的同学不难发现这与一种经典的排序算法（基数排序）非常类似。而基数排序的时间空间复杂度刚好符合题目要求。因此尝试使用基数排序来解这道面试题。

代码

/*———————————————* 日期：2015-02-19* 作者：SJF0115* 题目: 找重复元素* 来源：* 博客：———————————————–*/;class Solution {public:int IsReplication(int a[],int n){if(n <= 0){return -1;}//iffor(int i = 0;i < n;){if(a[i] != i){// 存在重复元素if(a[i] == a[a[i]]){return a[i];}//ifswap(a[i],a[a[i]]);}//ifelse{++i;}//else}//forreturn -1;}};int main() {Solution solution;int num[] = {6,1,4,7,5,3,6,2};int result = solution.IsReplication(num,8);cout<<result<<endl;}

思路二

第一次遍历：对于每一个A[i] = A[i] * n 第二次遍历：对于每一个i，A[A[i]/n]++ 第三次遍历：对于每一个i，A[i] % n就是出现次数 A[i]应该出现在A中的A[i]位置，乘以n、再除以n，很容易的来回变换；第二次遍历，对于A[i]本来所在的位置不断增1，，但绝对不对超出n的，那每一个i出现的次数，就是A[i]对n取余。

代码

/*———————————————* 日期：2015-02-20* 作者：SJF0115* 题目: 找重复元素* 来源：* 博客：———————————————–*/;class Solution {public:vector<int> Replication(int a[],int n){vector<int> result;if(n <= 0){return result;}(int i = 0;i < n;++i){a[i] *= n;}(int i = 0;i < n;++i){++a[a[i]/n];}count;for(int i = 0;i < n;++i){count = a[i] % n;if(count > 1){result.push_back(i);}//if}//forreturn result;}};int main() {Solution solution;int num[] = {6,1,3,7,5,3,6,2};vector<int> result = solution.Replication(num,8);for(int i = 0;i < result.size();++i){cout<<result[i]<<endl;}//for}

飞机一阵抖动，我终于说出了最后一句再见。