Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我正在寻找一种方法来在跳过列表中找到给定的元素 x,它是列表中的第 k 个(在它之前有 k-1 个元素)。算法的预期时间应该是 O(log K)
我找到了采用 O(log n) 的已知算法,但这里是 O(log K)。
提前谢谢你
您需要增加跳过列表,以便每个节点都有其“子树”中元素的计数(元素到其右下位置直到其级别中的下一个节点)。
很容易看出,您可以在不改变列表操作复杂性的情况下增加这些信息。
一旦你有了这个元数据,你只需要再上一层,直到下一层的节点已经离右边太远了。在这一点上,向下一层。
顺便说一下,这个问题被称为通过增广的动态订单统计。我从来没有在跳过列表中看到它,但是您可以找到有关如何使用其他有序树执行此操作的链接,这几乎是相同的想法。