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

解决方法: 简化题意得到,a[N]存了N-1个不重复的数,其中有一个数字是重复的,我们设为x。我们只需要建立一个b[N]数组,设里 面的N个数字都不重复,然后用b数组的和减去a数组的和,得到的就是最大的那个数字N减去重复的那个数字x得到的值。

代码如下:

int do_dup(int a[],int N)
{
 int b[N];
 int a_sum=0;
 int b_sum=0;
 for(int i=1;i<=N;i++)//建立一个数字不重复的数组b[N],然后计算出数组和
 {
     b[i-1]=i;
     b_sum+=b[N];
 }
 for(int i=0;i<N;i++)
 {
     a_sum+=a[i];
 }
 int value=b_sum-a_sum;
 return N-value;
}

优化算法:

int do_dup(int a[],int N)
{
 int sum1=0;
 int sum2=0;
 for(int i=1;i<N;i++)//算出1~N-1的数字和,即不重复的数字的和
     sum1+=i;
 for(int i=0;i<N;i++)//算出a数组的和
     sum2+=a[i];
 return sum2-sum1;
}