数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o(N)解决办法

数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o(N)
数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o(N)

C/C++ code

#include <stdio.h>int do_dup(int a[],int n);void main(){    int a[]={1,3,2,3};    do_dup(a,4);}int do_dup(int a[],int n){    int i;    int *b=new int[n];    for (i=0;i<n;i++)        b[i]=0;    for (i=0;i<n;i++)    {        if (b[a[i]]==0)        {            b[a[i]]=a[i];        }        else            printf("%d\n",b[a[i]]);    }    delete []b;    return 0;}

上面的代码有个问题，就是当重复的数为0时，就找不出来。
不知道大家有没什么好的算法

[解决办法]

引用楼主 w66187564 的帖子:

数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o(N)
...
就是当重复的数为0时，就找不出来。

[解决办法]
帮你略改了一下，且这个程序只有在 数组元素全部是自然数&&数组最大元素为9999时能用：
#include <stdio.h>
#define N 10000

void del(int a[],int n);
void main()
{
int a[]={1,3,2,3};
del(a,4);
}
void del(int a[],int n)
{
int i;
int *record=new int[N];
for (i=0;i<n;i++)
record[i]=-1;
for (i=0;i<N;i++)
{
if (record[a[i]]==-1)
{
record[a[i]]=a[i];
}
else
printf("%d\n",record[a[i]]);
}
delete []record;
}

查看更多 下一篇