数组列表算法 – 访谈
我今天在接受采访时被问到这个问题。 我尝试过一个解决方案，但想知道是否有更好的解决方法：
问题 ：我有一个arraylist说500,000个元素，使得arraylist的每个元素的值与索引相同。 例如：list.get（0）= 0; list.get（1）= 1 …等。 但只有一个元素与此排序不同步[即list.get（i）！= i]。 你怎么找到这个元素。
我的答案 ：使用多个线程迭代列表，每个线程在每次比较list.get（i）和i时处理arraylist的某个拼接。 找到元素后，设置一些布尔变量以向其他线程指示已找到该元素。
有没有办法解决这个问题而不迭代列表？ 还是更好的方法？
在最坏的情况下，您必须检查每个元素，因此无法改善O(n)时间复杂度。
考虑到这一点，最好的算法是从头到尾扫描arrays列表。 这样您就可以充分利用可用的内存带宽。
我不完全清楚线程是如何或为何进入图片的。 这似乎不合时宜。 这是问题的一部分吗？
答案是：一次迭代。 你提到原因的并发性是他们正在捕捉的东西。
实际上从java 8开始，解决方案是否并行很简单。 我认为最会带来：
OptionalInt foundInt = IntStream.range(0, list.size()) .parallelStream() .filter(i -> i != list.get(i)) .findAny();
你不能比O(n)做得更好。
其次，我认为在这些问题中谈论线程和multithreading是一个坏主意。 它们根本不感兴趣。 最后，你有一个O（无论如何）的运行时，你的常量被移除了。
也许面试官意味着一个排序数组，其元素从0到n-1，索引0到n-1。 然后将一个元素移动到不同的位置。 但这意味着所有剩余的元素都有不同的索引！ 在这种情况下，您可以使用二进制搜索改进搜索：
然后你可以在O(log n)获取元素。 从中间开始，检查索引是否等于元素。 如果相同则与半部的上半部分相同，如果不使用另一部分。
进一步了解@ aix的答案，如何对每个循环进行2次检查：
for (int i = 0; i < list.size / 2; i++) { if (i != list.get(i)) { return i; } else if (list.size - i != list.get(list.size - i) { return list.size - i; } }
1. iterate through the list 2. check for the condition in the elements 3. when that only element found break out the loop...
我不认为Thread进入竞技场……