给出一个存储可比较对象并支持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)
最佳答案
如果我收到这个面试问题,我会回答说我不知道任何此类数据结构,并且怀疑它们不存在。不过我怀疑面试官想的数据结构分别是“排序数组”和“跳表”。
然后我会解释按位置检索数组的任何元素的复杂度为 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)) 的查找数据以供插入使用,或者您需要创建道德上等同于双向链接的跳过列表。)
关于algorithm - 添加、获取第 k 个最大的数据结构是 O(log n) 和 O(1),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6024807/