java - 在数组中查找重复元素？

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) 中完成，然后只需要对相邻元素进行比较。或者只是将数组放入哈希表中，如果找到第一个键就停止有一个现有条目。