9

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

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

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

有没有办法在不遍历列表的情况下解决这个问题？还是更好的方法？

4

6 回答 6

13

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

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

我并不完全清楚线程是如何或为什么进入画面的。似乎不合时宜。这是问题的一部分吗？

于 2012-04-26T14:09:48.017 回答
6

答案是：一次迭代。你提到的原因并发是他们正在寻找的东西。

事实上，从 java 8 开始，是否并行的解决方案都很简单。我认为最会带来：

OptionalInt foundInt = IntStream.range(0, list.size())
    .parallelStream()
    .filter(i -> i != list.get(i))
    .findAny();
于 2016-08-11T14:49:45.393 回答
2

你不能做得比O(n).

其次，我认为在这些问题中讨论线程和多线程是一个坏主意。他们根本不感兴趣。最后，你有一个 O(whatever) 的运行时，无论如何你的常量都会被删除。

也许面试官的意思是一个排序数组，其元素从 0 到 n-1，索引从 0 到 n-1。然后将一个元素移动到不同的位置。但这意味着所有剩余的元素都有不同的索引！在这种情况下，您可以使用二分搜索改进搜索：

然后你可以在O(log n). 从中间开始，检查索引是否等于元素。如果相等，则对上半部分执行相同操作，否则使用其他部分。

于 2012-04-26T14:11:07.170 回答
0

除了@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;
  }
}
于 2012-04-26T14:19:42.163 回答
0 
1. iterate through the list 
2. check for the condition in the elements
3. when that only element found break out the loop...

我不认为线程进入竞技场......

于 2012-04-26T14:23:38.387 回答
0 
ArrayList<Integer> s = new ArrayList<Integer>();

for (int i=0; i<500000; i++) {
    s.add(i);
}

s.set(13, 500002);

for (int j=0; j<s.size(); j++) {
    if (j != s.get(j)) {
        System.out.println(j + " " + s.get(j));
    }   
}
于 2019-12-09T06:27:59.310 回答