数组列表算法 - 访谈

Question

我今天在接受采访时被问到这个问题.我尝试了一个解决方案,但想知道是否有更好的解决方法:

问题:我有一个arraylist说500,000个元素,使得arraylist的每个元素的值与索引相同.例如:list.get(0)= 0; list.get(1)= 1 ...等.但只有一个元素与此排序不同步[即list.get(i)!= i].你怎么找到这个元素.

我的答案:使用多个线程迭代列表,每个线程处理一个arraylist的某个拼接,每次比较list.get(i)和i.找到元素后,设置一些布尔变量以向其他线程指示已找到该元素.

有没有办法解决这个问题而不迭代列表？还是更好的方法？

Answer 1

在最坏的情况下,您必须检查每个元素,因此您无法改善O(n)时间复杂度.

考虑到这一点,最好的算法是从头到尾扫描阵列列表.这样您就可以充分利用可用的内存带宽.

我并不完全清楚线程是如何或为何进入图片的.这似乎不合时宜.这是问题的一部分吗？

Answer 2

答案是：一次迭代。您提到的原因并发是他们追求的目标。

实际上从Java 8开始，不管是否并行，解决方案都很简单。我认为最能带来的是：

OptionalInt foundInt = IntStream.range(0, list.size())
    .parallelStream()
    .filter(i -> i != list.get(i))
    .findAny();