在线性时间内准备数组，以在O(k)时间内找到k个最小元素。

Question

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

我已经与一些朋友讨论了这个问题，但没有人能找到解决方案，任何帮助将不胜感激！

- Idan

---

无法确定数据类型，因此无法使用基数排序，因为它只适用于整数。 - Idan

这个数组中的元素是否唯一？ - Bill

生成的元素必须按顺序呈现吗？ - Juan Guerrero

Bill- 元素是数字（整数和非整数）。 Juan- 元素的顺序不重要。 Larsmans- 这是一个好观点。然而，在预处理时间中，我们不知道k的值。 - Idan

@JuanGuerrero 显然，答案不必按顺序呈现，否则对于 k = n 的情况，需要在没有任何预先信息的情况下以 O(n) 的时间复杂度对数组进行排序。 - i Code 4 Food

Answer 1

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

使用该算法找到第 n/2 个数字...现在将数据集划分为两半，下半部分和上半部分。在下半部分中再次找到中点。在其下半部分执行相同的操作，并且依此类推......总体而言这是 O(n) + O(n/2) + O(n/4) + ... = O(n)。

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

- Karoly Horvath

---

我认为这相当不直观。即使您必须以相同的速度检索所有元素，您仍会更多地预处理较早的元素。基本上，您正在利用先前的元素可以“支付”检索后续元素的事实。例如，如果k=n/2+1，则获取前n/2个元素需要n/2的时间，但获取最后一个元素也需要n/2的时间。但没关系，因为2·n/2仍然是O(n/2+1)。 - svick

嗨，我应该继续在上半部分进行分区过程以再次找到中点吗？如果不是，那么在k大于n/2的情况下，我该如何找到k个最小元素？ - Idan

最后一句话中的选择算法是否能以O(k)的时间复杂度工作？ - Idan

1. 不，你只需要对下半部分进行操作。如果k大于n/2，则返回下半部分中的所有元素，再加上来自上半部分的k-n/2个元素。
2. 是的，那里有O(k)个元素。请检查您的最后一个示例，该分区具有n/2个元素，小于k。

- Karoly Horvath

@svick：我认为在某种程度上它很直观。如果k足够大（就像你的例子中，>n/2），你甚至不需要预处理，因为选择算法将在O(k)内完成。随着k变得越来越小，更需要预处理来确保您只需检查少量元素。 - Karoly Horvath

Answer 2

我们可以在线性时间内找到列表的中位数并围绕它进行分区。

然后我们可以使用以下算法：维护一个大小为2k的缓冲区。

每当缓冲区变满时，我们找到中位数并围绕它进行分区，仅保留最低的k个元素。这需要n/k次查找中位数和分区步骤，每次使用传统的快速选择需要O(k)的时间。这种方法只需要O(n)的时间。

此外，如果您需要排序输出，则需要额外的O(k log k)时间。总体而言，这种方法只需要O(n + k log k)的时间和O(k)的空间。

- Jayram

---

这没有任何意义。这里的预处理步骤是什么？看起来你描述的整个过程都不包括这一步，但是这一步无法知道 k。我甚至不理解这应该如何工作。 - Karoly Horvath