0

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

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

提前谢谢你

4

1 回答 1

1

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

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

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


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

于 2015-05-17T16:46:48.200 回答