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

如题所述

算法思想:先对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)

算法特点:对于数组中数值的出现顺序不做任何要求,即无需有序(这是二楼算法的缺陷)。
温馨提示:答案为网友推荐,仅供参考
第1个回答  2011-05-02
#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, 那么我们就可以根据这个来找到重复的数据了,即只要前面这个等式不成立,那么这个数就找到了,输出即可。本回答被网友采纳
第2个回答  2011-05-02
a[N]中存放了的数的范围是1至N-1吗?

相关了解……

你可能感兴趣的内容

本站内容来自于网友发表,不代表本站立场,仅表示其个人看法,不对其真实性、正确性、有效性作任何的担保
相关事宜请发邮件给我们
© 非常风气网