链表，在log(k)中实现peekAt(k)方法

Question

我被要求设计一个数据结构，它的作用类似于堆栈，不受大小限制，它将支持以下方法，但有给定的运行时限制。

推送- 将 s 推送到数据结构 - O(1(pop(( - 删除并返回插入的最后一个元素 O(1(middle((- 按插入顺序返回索引为 n/2 的元素(不删除(，其中 n 是数据结构中当前元素的数量。- O(1(peekAt(k( - 按插入顺序返回第 k 个元素(堆栈底部为 k=1( - O(log(k((

这 3 个方法将使用链表，但我应该如何实现方法 peekAt(k(。

谢谢。

Answer 1

您要查找的是"跳过列表"的变体，该列表按广告顺序排序。

为了支持O(logk)而不是O(logn)，您实际需要的唯一修改是在开始搜索之前从下到上，如下所示：

// Assume head points to the first element in the lower tier list.
current = head
while (current->next->index < k) current = current->up

此时，您要查找的元素介于current和current->next之间。您可以使用常规的跳过列表搜索值k查找它，从current而不是顶层开始。

请注意，查找current是在O(logk)中完成的，因为您基本上是迭代检查：

1 < k ?
2 < k ?
4 < k ?
8 < k ?
...
2^ceil(logk) < k ?

也就是说，O(log(k((检查。