algorithm - 检测数字数组是否具有相同数字的最佳算法

Question

算法只需要检测是否有至少2个数字相同。

我图片中的那个是最好的方法还是有更有效的方法。

这是书本上的任务，如果我做对了，我不会拒绝。

算法

Answer 1

如果数组是有序的:

for(int i=0; i<a.length-1; i++)
  if(a[i]==a[i+1])
    return true;
return false;

如果数组没有排序，使用缓存:

boolean[] cache=new boolean[N];
Arrays.fill(cache,false); //set all values to false

for(int i=0; i<a.length; i++)
  if(cache[a[i]])
    return true;
  else
    cache[a[i]]=true; //mark element a[i] as seen
return false;

在上面，N是数组a中出现的最大值。如果 N 未知或非常大，或者您的数组包含负值，请使用映射而不是数组作为缓存。

两种解决方案都在 O(n) 时间内运行。第二种解决方案只需要一个外部缓存来记住我们之前见过的元素。