数组列表算法 - 面试 [英] Array list algorithm - Interview

问题描述

我今天在接受采访时问这个问题。我试过一个解决方案，但想知道是否有一个更好的方法来解决这个：

I was asked this question in an interview today. I have tried a solution but would like to know if there's a better way to solve this:

问题：我有一个arraylist说500,000元素，以便arraylist的每个元素的值与索引相同。例如：list.get（0）= 0; list.get（1）= 1 ... etc。但是只有一个元素与这个排序不同步[即list.get（i）！= i]。如何找到该元素。

Question: I have an arraylist say of 500,000 elements such that the value of each element of the arraylist is same as the index. For ex: list.get(0) = 0; list.get(1) = 1 ...etc. But only one element is out of sync with this ordering [i.e list.get(i) != i]. How do you find that element.

我的回答：使用多线程迭代列表每个线程处理一个阵列表比较list.get（i）和i。当元素被找到时，设置一些布尔变量来指示其他线程已经找到该元素。

My Answer: Iterate over the list using multiple threads each thread handling a certain splice of the arraylist each time comparing list.get(i) with i. When the element is found, set some boolean variable to indicate to other threads that the element has been found.

有没有办法解决这个问题， ？

Is there a way to solve this problem without iterating over the list? Or a better way?

推荐答案

在最坏的情况下，你必须检查每个元素，所以你不能改进 O（n）时间复杂度。

In the worst case you have to examine each element, so you can't improve on the O(n) time complexity.

考虑到这一点，最好的算法是从开始扫描数组列表完成。这样，您就可以充分利用可用的内存带宽。

With this in mind, the best algorithm is to scan the array list from start to finish. This way you're making best use of the available memory bandwidth.

我并不完全清楚如何或为什么线程进入了图片。它似乎不合适。这是问题的一部分吗？

It is not entirely clear to me how or why threading has entered the picture. It seems out of place. Was it part of the question?

这篇关于数组列表算法 - 面试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！