在数组中查找重复元素？

Question

我看到一个面试问题如下:

数组中的一个数字是重复的.找到它

简单的解决方案如下:

for(int i=0;i<n;i++){
{  
    dup = false;
    for(j=0;j<n;j++){
        if(i!=j && a[i]= a[j]){
            dup = true;
        }

       if(dup == true)
          return a[i]
     }
}

但我想在O(n log(n))和O(n)时间内实现它.我该怎么做？

Answer 1

对数组进行排序(可以在第一个O(n Log n)中完成,然后只需对相邻元素进行比较.或者只是将数组放入哈希表中并在找到第一个带有exsting的键时停止条目.