Question

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

Answer 1

算法思想：先对1..N-1之间的所有整数累加求和，再对数组中的所有元素累加求和；用后者减去前者得到的差就是重复的数字。

参考源代码(C++)：

#include "iostream.h"

void main()
{
int arr[] = {6, 2, 3, 4, 3, 5, 1};
int N = 7;
int sum1, sum2;
int i;

for(i=1,sum1=0; i<N; sum1+=i,i++);

for(i=0,sum2=0; i<N; sum2+=arr[i],i++);

cout<<"重复的数字是 "<<sum2-sum1<<endl;
}

时间复杂度：O（n）

算法特点：对于数组中数值的出现顺序不做任何要求，即无需有序（这是二楼算法的缺陷）。

Answer 2

#include<stdio.h>
#define N 10

int main()
{
int array[N]={1,2,3,4,5,2,6,7,8,9};
int i;
for(i=0;i<N;i++)
{
if(array[i]!=i+1)
break;
}

printf("repeat num is:%2d\n",array[i]);

return 0;
}
如果不进行初始化的话，就还需要一个for循环来初始化，语句为：
for(i=0;i<N;i++)
array[i]=i+1;这样就行了，
具体的算法就是：从1到N-1有n-1个数，所以，重复的数只有一个，而且数组的值有一定的规律，即array[i]=i+1, 那么我们就可以根据这个来找到重复的数据了，即只要前面这个等式不成立，那么这个数就找到了，输出即可。

Answer 3

a[N]中存放了的数的范围是1至N-1吗？