数组列表算法 - 面试

Question

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

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

我的答案：使用多个线程迭代列表，每个线程处理列表的某个部分，每次将list.get(i)与i进行比较。当找到该元素时，设置某些布尔变量以指示其他线程已找到该元素。

有没有一种不迭代列表的方法来解决这个问题？或者有更好的方法吗？

- sachinrahulsourav

---

没有任何关于这个数字可能在列表中的位置的提示，这个问题有点无聊。 - keyser

我认为你必须解释一下"只有一个元素不同步"到底是什么意思...这听起来毫无意义...请看下面我的回答。我认为，如果你移动一个元素，所有剩余的元素都会不同步，不是吗？ - duedl0r

@dued0r 元素未被移除。面试官问如何识别值与索引不同的元素。 - sachinrahulsourav

我认为这不是找到同时访问不同区域的方法...而是更多地减少数据访问... - Mehdi

Answer 1

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

基于此，最佳算法是从头到尾扫描数组列表。这样您可以充分利用可用的内存带宽。

我不太清楚线程如何或为什么出现在图片中。似乎不合适。它是问题的一部分吗？

- NPE

---

这个问题这样问有点无聊，虽然我同意你的观点。 - zw324

@aix 不是的，那是我对面试官的回答。我一开始认为使用数组切片并处理数组列表的迭代实际上会更好，但后来意识到即使使用多个线程也无法改进O(n)。事实上，线程只会引入更多复杂性。 - sachinrahulsourav

虽然你可以在同一个循环中从列表的两端解决问题。 - Nick Holt

@NickHolt：嗯，有很多方法可以尝试部分展开那个循环。但是需要进行性能分析才能对性能影响做出有意义的陈述（当然它不会改变O(n)）。 - NPE

是的，如果内存I/O成为瓶颈，增加线程也无济于事。大多数CPU只有一个外部内存接口，因此在多个核心上增加更多线程也没有帮助。 - Steve Kuo

Answer 2

答案是：一次迭代。你提到的并发问题是他们想要了解的内容。

实际上，自Java 8以来，无论是并行还是非并行，解决方案都很简单。我认为大多数人都会选择：

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

- Joop Eggen

Answer 3

你再好不过了，时间复杂度为O(n)。

其次，在这些问题中谈论线程和多线程是个坏主意。它们根本没有任何意义。最终您的运行时是O(whatever)，其中您的常数已经被移除。

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

然后您可以在O(log n)的时间内获取元素。从中间开始，并检查索引是否等于元素值。如果相等，则对上半部分重复此操作，否则请使用另一半。

- duedl0r

---

我同意。而且对于现在的单个线程来说，500,000甚至都不算多。 - keyser

你的 O(log n) 算法似乎在列表 1, 0, 2, 3, 4, 5 上失败了。你是想移动(move)还是删除(remove)？如果是删除，那么它可以正常工作。 - btilly

@btilly 我认为他的意思是，如果一般规则是 f(n+1)=f(n)+1（除了那个特定的目标），那么这里最理想的方法是二分查找。 - HelloWorld

@btilly：为什么它在这个列表上失败了？我将在O(log n)中找到元素0。在这种情况下，每个元素都有不同的索引。因此我们要查找索引0... - duedl0r

@duedl0r，我将元素1移动到元素0，但其他所有元素的索引都没有改变。因此，当您查看中点时，会发现它并没有改变，并且会在上半部分查找。 - btilly

@JingtengXue 我同意你的规则版本是可行的。然而，我在挑剔“将一个元素移动到不同的位置”并不能使列表符合该描述。 - btilly

Answer 4

回复 @aix 的答案，每个循环进行两次检查如何：

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;
  }
}

- Nick Holt

---

我的观点是，在没有性能基准的情况下，循环展开最好留给JIT编译器处理。 - NPE

@aix 是的，我同意，就可读性而言，我会避免做这样的事情。 - Nick Holt

Answer 5

1. iterate through the list 
2. check for the condition in the elements
3. when that only element found break out the loop... 

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

- Parth Soni

Answer 6

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));
    }   
}

- Kishankumar Sanapala