IT虾米网

java之数组列表算法——面试

iiiiii 2023年10月05日 编程语言 107 0

我今天在采访中被问到这个问题。我已经尝试了一种解决方案,但想知道是否有更好的方法来解决这个问题:

问题:我有一个包含 500,000 个元素的数组列表,这样数组列表的每个元素的值都与索引相同。例如:list.get(0) = 0; list.get(1) = 1 ...等等但是只有一个元素与此顺序不同步 [即 list.get(i) != i]。你如何找到那个元素。

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

有没有办法不用遍历列表就可以解决这个问题?或者更好的方法?

请您参考如下方法:

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

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

我并不完全清楚线程如何或为何进入画面。似乎格格不入。这是问题的一部分吗?


评论关闭
IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!