algorithm - 如何在跳过列表中搜索元素

Question

我正在寻找一种方法来在跳过列表中找到给定的元素 x，它是列表中的第 k 个（在它之前有 k-1 个元素）。算法的预期时间应该是 O(log K)

我找到了采用 O(log n) 的已知算法，但这里是 O(log K)。

提前谢谢你

Answer 1

您需要增加跳过列表，以便每个节点都有其“子树”中元素的计数（元素到其右下位置直到其级别中的下一个节点）。

很容易看出，您可以在不改变列表操作复杂性的情况下增加这些信息。

一旦你有了这个元数据，你只需要再上一层，直到下一层的节点已经离右边太远了。在这一点上，向下一层。

---

顺便说一下，这个问题被称为通过增广的动态订单统计。我从来没有在跳过列表中看到它，但是您可以找到有关如何使用其他有序树执行此操作的链接，这几乎是相同的想法。