algorithm - 添加、获取第 k 个最大的数据结构是 O(log n) 和 O(1)

Question

给出一个存储可比较对象并支持add()的数据结构和 get(k)操作[ get(k)返回数据结构中第 k 个最小的元素 (1 <= k <= n) ]. get(k)必须是 O(1)和 add()必须是 O(log n)其中 n 是添加到数据结构中的对象数。给出另一个结构，其中 get(k)是O(log n)添加是O(1)

Answer 1

如果我收到这个面试问题，我会回答说我不知道​​任何此类数据结构，并且怀疑它们不存在。不过我怀疑面试官想的数据结构分别是“排序数组”和“跳表”。

然后我会解释按位置检索数组的任何元素的复杂度为 O(1)。找出插入它的位置是 O(log(n))。然而，由于必须移动数组的其余部分，实际插入是 O(n)。然而，O(n) 部分带有非常好的常数。

对于跳过列表，检索是 O(log(n))。插入涉及一半时间只修改一个元素，1/4 时间编辑 2，1/8 时间编辑 3 等等，这是平均 2 个元素。那是 O(1)。但是，您无法在不知道将元素放在哪里的情况下插入元素。该查找是 O(log(n))。 (要使插入真正成为 O(1)，您需要收集 O(log(n)) 的查找数据以供插入使用，或者您需要创建道德上等同于双向链接的跳过列表。)