最近和算法干上了,数组算法大讨论拉

Question

数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，要求：找出被重复的数字.时间复杂度必须为o（N）。大家有什么好招。各显神通拉。

Answer 1

怎么大家怎么冷淡。斑竹你们也应该出来。发表发表啊。====CSDN 小助手 V2.5 2005年11月05日发布====
CSDN小助手是一款脱离浏览器也可以访问Csdn论坛的软件
界面：http://blog.csdn.net/Qqwwee_Com/archive/2005/11/05/523395.aspx
下载：http://szlawbook.com/csdnv2

Answer 2

空间换时间，再构造一个大数组，设为数组b，原来设为数组a遍历数组a，假设a[1]=99，则b[99]＝1，遍历中设a[x]=m，如果b[m]=1，则m为重复数

Answer 3

利用Hashtable吧，将值作为哈西表的键存入，当发现以当前值作为键的元素存在，那么当前值就是重复的值

Answer 4

先数组进行排序.
然后一个for循环就搞定了.

Answer 5

请贴代码出来看看。学习学习====CSDN 小助手 V2.5 2005年11月05日发布====
CSDN小助手是一款脱离浏览器也可以访问Csdn论坛的软件
界面：http://blog.csdn.net/Qqwwee_Com/archive/2005/11/05/523395.aspx
下载：http://szlawbook.com/csdnv2

Answer 6

public return_array(int[] a,ref int[] b,int num)
{
   int j=0;
   for(int i=0;i<a.Length-1;i++)
   {
      if(a[i]==num)
      {
         b[j]=a[i];
         j++;
      } 
   }
   b[j]=-99999;//结束标志 
}

Answer 7

以上的时间复杂度为0(n),无法做出时间复杂度为0(X)（X为常数）的算法。

Answer 8

看错命题了，不过你这个算法好像时间复杂度无法做到O(N),要做到O(N2)（平方）很容易。

Answer 9

System.Collections.Hashtable ht = new Hashtable();
for(int i=0;i<a.Length;i++)
{
    if(!ht.ContainsKey(a[i]))
    {
        ht.Add(a[i],i);
    }
    else
    {
        //索引为i的元素是重复的
    }
}

Answer 10

int[] a = ....
a.Sort();
if(a.Length > 1)
{
for(inti =1;i<a.Length;i++)
{
if(a[i-1] == a[i])
{
return a[i];
}
}

Answer 11

System.Collections.Hashtable ht = new System.Collections.Hashtable();
for(int i=0;i<a.Length;i++)
{
    if(!ht.ContainsKey(a[i]))
    {
        ht.Add(a[i],i);
    }
    else
    {
        //索引为i的元素是重复的
    }
}

Answer 12

如果a.Sort占用时间复杂度,那的另想办法了.