algorithm - 在线性时间内准备数组以找到 O(k) 中的 k 个最小元素

Question

这是我在网上发现的一个有趣的问题。给定一个包含 n 的数组数字(没有关于它们的信息)，我们应该在线性时间内预处理数组，以便我们可以返回 k 中的最小元素 O(k) 时间，当我们得到一个数字 1 <= k <= n

我一直在和一些 friend 讨论这个问题，但没有人找到解决方案；任何帮助将不胜感激!

Answer 1

对于预处理步骤，我们将在同一数据集上多次使用基于分区的选择。

使用算法找到第 n/2 个数。现在数据集被分成上下两半。在下半部分再次找到中点。在其较低的分区上做同样的事情等等......总的来说这是 O(n) + O(n/2) + O(n/4) + ... = O(n)。

现在，当您必须返回 k 个最小元素时，搜索最近的 x <k，其中 x 是分区边界。它下面的所有内容都可以返回，并且您必须从下一个分区返回 k - x 个数字。由于下一个分区的大小是 O(k)，为第 k - x 个数字运行另一个选择算法将返回其余部分。