求助，一个算法题

Question

有一个数组a[1000]，其中有999个数是不同的数，还有一个是重复的数，用最快的方法把这个重复的数找出来

Answer 1

在SQL中方便SELECT ID FROM TB GROUP BY ID HAVING COUNT(ID)>=2

Answer 2

for（int i=0；i<1000;i++）
for（int j=i+1；j<1000;j++）{
  if(a[i]==a[j])
{
    //find it 
    break;
}
}

Answer 3

        static void Main(string[] args)
        {
            List<int> listsA = new List<int>();
            List<int> listsB = new List<int>();
            Random rand=new Random();
            for(int i=1;i<1000;i++)
            {
                listsA.Add(i);
            }
            listsA.Add(rand.Next(1000));            for (int i = 0; i < listsA.Count; i++)
            {
                if (!listsB.Contains(listsA[i]))
                {
                    listsB.Add(listsA[i]);
                }
                else
                {
                    Console.WriteLine(listsA[i]);
                    break;
                }
            }
            Console.ReadLine();
        }

Answer 4

其实既然知道1000个里面有999个不一样的，那可以这么做，使用一个数组A[1000]，初始全部是0，每个表示一个数，开始扫描，一旦对应的数字为A的下标+1，那么相应的A[]的flag加1，这样最多次数是O(2n)

Answer 5

楼上的，怎么会是0(2n)呢？
应该是0(n * n)。

Answer 6

就是n+n，2n，不知道你的n*n怎么得出的结果。我第一次扫描相当于构建了一个Hash表，第二次的时候只需要扫描一次，看我构建的值是不是等于2即可

Answer 7

int sum1,sum2;
for(int i=0; i<=99; i++)
{
   sum1+=a[i];
   sum2+=i;
}return sum1-sum2;

Answer 8

int sum1,sum2;for(int i = 0;i<999;i++)
{sum1+=a[i];
sum2+=i;
}
return sum1-sum2;

Answer 9

sum(a) - 999*500
其中sum(a)是数组a中所有数据的和
或者
int b=0;
int i;
for(i = 0; i < 1000; i++) {
   b ^= i+1;
   b &= a[i];
}
return b;
b 就是要求的那个数了

Answer 10

sum(a) - 999*500 
其中sum(a)是数组a中所有数据的和 
或者 
int b=0; 
int i; 
for(i = 0; i < 1000; i++) { 
  b ^= i+1; 
  b ^= a[i]; 
} 
b ^= 1000;
return b; 
b 就是要求的那个数了
之前那个写错了。

Answer 11

感觉跟 有一千个X，其中有一个跟其他999个X不同重量的Y，只用一次就那个Y给找出一样