用O(n)初始化和O(1)查找编写数据结构

Question

给定数组a1, a2, a3, ... , aN

我想要创建一个支持以下需求的数据结构：

• O(n)中的初始化数据结构
• 得到O(1)中的4n/5值
• 求O(1)中的n/5值

我试图用3个最大堆来构建数据结构，但无法在O(n)中初始化堆。

我怎么才能弄清楚？

Answer 1

所谓的"median of medians" algorithm可以在O(n)时间内的无序集中找到kth最小元素。您希望将此应用于k= n/5和k= 4n/5。

算法的结果是一个部分有序的数组，其中所需的kth元素位于k位置，在将n/5元素置于其位置后，我认为可以将4N/5元素放在它的位置，而不必重新执行整个算法，但无论如何，它仍然是O(n)。

假设数组中有O(1)随机访问查找，那么O(1)查找需求将得到满足。