算法题，请提供解决方案

Question

一个1000个元素的整型数组x,对于它的每一个元素x[i],都满足1<=x[i]<=1000,设计一个算法，检查该数组中是否有重复元素，O(n)复杂度。

Answer 1

求和比较，数组的和(sum(x))来比较1到1000的和(= 500*1001 = 500500)

Answer 2

采用散列方法。最简单的就是使用1个 counter[1000]的数组。
记录每一个值的出现次数。这样只需要2个for循环，扫描就可以了。
o（n）

Answer 3

[code=C++]
const int Size = 1001;
int counter[Size];  //init counter[i]= 0;
int data[Size];for(int i=0;i<Size;++i)
{
    int index = data[i];
    ++counter[index];
}bool dup = false;
for(int i=0;i<Size;++i)
{
    if(counter[i]>1)
    {
       dup = true;
    }
}[/code]

Answer 4

ps：散列的想法就是空间换时间，因为即使是快排也不能实现o(n)，所以直觉马上就是散列。

Answer 5

不好意思，刚才没注意，明白了，谢谢Efcndi