讨论一个算法

x4ulocca

n个整数，其中有2个相同，请设计算法将此数找出来。算法复杂度要求为O(n).

tyc611

如果对空间复杂度没要求，那这个时间复杂度很容易办到

uclinux_arm9

#include<stdio.h>
main()
{
int a[] = {1,2,3,4,5,5,6,7,8,9,10};
const int len=sizeof(a)>>(sizeof(int)>>1);
int count[sizeof(a)>>(sizeof(int)>>1)]={0};
register int idx=0;
int nResult=-1;
for(idx=0;idx<len;idx++)
  {  if( ++count[a[idx]]>1){nResult=idx;break;};
}
printf("index=%d        a[%d]=%d\n",nResult,nResult,a[nResult]);
}

醉卧水云间

O(n) 应该做不到.

DraculaW

如果对空间要求不大 就随便用个线性排序的算法就可以做出来的哦 呵呵
box sort
count sort 之类的都好啊

blackuhlan

算法复杂度为O(n)是个新概念，能否解释一下。(兄弟确实不知道)
如果时间复杂度为O(n),那你可以试一下
if( a1+a3... == a2 + a4...)
{
   if( a1+a4+a7... == a2+a5+a8...)
   ...
}
else
{
   ...
}

blackuhlan

如果是空间复杂度为O(n),那么这个就是一个二重循环的问题，大家都会，就不多说了

DraculaW

6樓你寫的  呃.....  基本上太不現實了  這個程序的速度快但是寫的人就要累死了啊

算法一個重要的特性就是易于實現

就用一些綫性時間的排序就可以了麽 呵呵

DraculaW

二重循环？

譬如說

flw

晕～
咋不要求是 O(1) 呢？