攻克名企面试题，剑指心仪offer！——题目1数组中重复的数字面试xiaomuY的博客-

        你还在为找不到心仪的offer发愁吗？还在为面试担心吗？和我一起，提起剑来，攻克面试的种种难关！直指心仪offer！！！

题目一：在一个长度为n的数组里所有元素都在0~n-1范围内，数组中可能有某些数是重复的，但不知道那些数重复了，也不知道重复了几次。请找出任意一个重复度数字。

分析：

方法一：

        先把数组排序，然后再从头到尾扫描就可以了。排序的时间复杂度为O(n*logn)的时间。

方法二：

        创建一个哈希表，从头到尾依次扫描，每扫描一个数，然后判断哈希表里是否已将有这个数了，如果没有，就把该数加入哈希表，如果已经有了，则表明找到了一个数。此方法时间复杂度为O（n），比方法一要好很多，但是要建立哈希表，空间复杂度却为O(n)。
        那有没有更好的方法让空间复杂度也降低呢？答案肯定是有的。

方法三：

        我们注意到，共有n个元素，范围是0~n-1，那么，在不重复的时候，排序后元素值和下标是相等的。由于有重复的数字，那么，当再次把数据放到和它自身相等的下标处时，有些下标是没有元素的，而有些地方一个下标对应好几个元素。

        那我们就可以依次把每个元素放到和它自身相等的下标处来看一看。首先我们设一个数组a[10]从第一个元素开始，依次比较元素值m(假设a[i]=m)和下标i是不是相等，如果是，在扫描下一个元素，如果不是，则将a[i]和a[m]交换，则m就到了属于它的地方。这样进行下去，如果有重复的数字，总会有一个下标处出现两个值都为m的元素。

        如果不好理解的话，我们举一个例子。以a[10]={1,4,2,8,5,4,3,7,8,7}为例。

首先：要比较a[0]是否为0，结果a[0]=1，交换a[0]、a[1]得{4,1,2,8,5,4,3,7,8,7}。

继续比较a[0]是否为0，结果a[0]=4，交换a[0]、a[4]得{5,1,2,8,4,4,3,7,8,7}。

继续比较a[0]是否为0，结果a[0]=5，交换a[0]、a[5]得{4,1,2,8,4,5,3,7,8,7}。

继续比较a[0]是否为0，结果a[0]=4，交换a[0]、a[4]得{4,1,2,8,4,5,3,7,8,7}。

        我们发现a[0]、a[4]重复了，都为4。由于每个数最多交换两次就能到自己的位置上，因此时间复杂度为O(n),另外，整个过程不需要额外空间，因此空间复杂度为O(1),比起前两种方法好的多了。

代码如下：

#include<stdio.h> void Seek_Repeat_Number(int *a,int len) { int i=0,m=0; if (a == NULL || len <= 0) { printf("空数组!n"); return; } for (i=0; i < len; i++) { if (a[i]<0 || a[i]>len - 1) { printf("数组数据不满足题目要求!n"); return; } } for (i = 0; i < len; ++i) { while (a[i] != i) {    m = a[i]; if (a[i] == a[m]) { printf("%d重复了n",a[i]); return; } else { int x = a[i];     a[i] = a[m];     a[m] = x; } } } } int main() { int a[20]; int x = 0, i = 0,len=0; printf("请输入一个数组（元素个数不能超过20）,以“-1”结束!n"); while (scanf("%d", &x), x != -1) {   a[i] = x;   len++;   i++; } Seek_Repeat_Number(a,len); return 0; } 

运行结果：

文章系本人原创，转载请注明作者和出处。