找到未知大小列表的中间位置

Question

最近在一次面试中，我被问到：

找到一个从第一个位置开始的未知长度的排序列表的中间元素。

我的回答如下：

有两个位置计数器：

counter1 counter2

将counter1增加1，将counter2增加2。当counter2达到列表的末尾时，counter1将位于中间。我认为这不是很有效，因为我会重复查看已经看过的节点。 无论如何，是否有更有效的算法？

- segFault

---

这个算法时间复杂度为 O(N)，空间复杂度为 O(1)。这看起来相当不错。 - PengOne

如果长度未知，哪些操作是允许的？这是一个链表吗？ - Vlad

我在想你可以做类似的事情，但是使用相同的计数器，而不是跳2，跳一个更大的数量。跳跃由1跳跃的计数器的距离，当到达边界时再加1。这样做是否更好，无效或有缺陷？ - segFault

面试官当时的回答是什么？ - cyber_raj

@segFault：为了给出最佳答案，需要共享列表类型（或至少允许的操作）。Strilanc针对链表给出了很好的答案（+1）。我则为基于数组的列表给出了我认为是最优解（你之前的评论似乎暗示了这一点）。 - Eric J.

Answer 1

假设有一个链表，你可以在访问接近 N 个项目的情况下完成它。

要完成5/4 N：

- 迭代列表直到到达末尾，计算项数。 - 在2的幂位置处设置锚点。跟踪最后2个锚点。 - 迭代倒数第二个锚点，直到它达到列表中点。

当你到达列表末尾时，倒数第二个锚点位于中点之前，但已经至少完成了一半的距离。因此，完整迭代的N加上最多1/4 N的锚点就是5/4 N。

更频繁地设置锚点，例如在每个1.5的幂位置处设置锚点，可以使你达到所需的接近 N 的效果（代价是跟踪更多的锚点；但对于任何给定的X作为步长，渐近内存是常数）。

- Craig Gidney

---

很棒的答案。不过我不确定二分查找有什么用处；如果是针对数组，我们可以从一开始就做得更好。 - davin

我指的是一个数组，你不知道确切的长度，但可以检查给定位置是否超过了长度。也许它是一个没有误报和0..N插入的布隆过滤器。我会删除那个情况，因为它太奇怪而微不足道了。 - Craig Gidney

@Strilanc 如果你找到了一种可以不出现误判的布隆过滤器，请告诉我们。 - Nick Johnson

Answer 2

我假设您正在讨论一个链表。实际上，您的解决方案是非常好的。另一种方法是简单地遍历列表，计算元素数量，然后从开头重新开始，遍历计数的一半。这两种方法最终都会遍历3n/2个节点，所以差别不大。

可能根据架构的不同，两种方法之间可能存在轻微的缓存优势；第一种方法可能具有缓存节点的优点，在两个指针相距太远之前，如果缓存足够大，则意味着更快的检索。或者，如果我们一次遍历列表而不是保持两个指针活动，那么缓存可能会得到更好的块。

- davin

Answer 3

假设您能够检测到已经超出了列表的末尾，并且能够有效地在列表中寻找任意位置，那么您可以不断将列表长度加倍（猜测长度为1，然后2，然后4，...），直到您超出了列表的末尾，然后使用二分查找在小于列表长度的最后一个尝试值和首个超过列表末尾的值之间找到实际的列表末尾。

然后，在位置END_OF_LIST / 2处查找。

这样，您就不必访问每个节点了。

- Eric J.

Answer 4

假设常规的内存链表允许多次读取给定当前引用的下一个元素（免责声明，未经测试，但这个想法应该可行）：

// assume non-empty list
slow = fast = first;
count = 0;

while (fast)
{
  fast = fast.next;

  if (!fast)
    break;

  count++;
  fast = fast.next;

  if (fast)
    count++;

  slow = slow.next;
}

if (count % 2)
  return slow.data;
else
  return (slow.data + slow.next.data)/2.0;

一个更困难的情况是，当“列表”不是内存中的链表，而是一个可以按排序顺序读取并且每个元素只需读取一次的流时，我没有一个好的解决方案。

- Sasha Pachev

Answer 5

从技术上讲，如果您使用链表，可以在一次遍历中使用O（N）内存来完成此操作。

1. 遍历列表并将其转换为数组（如果这是链表，则为指针数组）。
2. 返回arr [N / 2]

编辑：我确实喜欢您的答案！

- kyun