这是我在网上找到的一个有趣的问题。给定一个包含数字的数组n（没有关于它们的信息），我们应该在线性时间内对数组进行预处理，以便在给定一个数字时及时返回k最小的元素O(k)1 <= k <= n
我一直在和一些朋友讨论这个问题，但没有人能找到解决办法；任何帮助，将不胜感激！
问问题
1295 次
2 回答
15
对于预处理步骤，我们将在同一数据集上多次使用基于分区的选择。
用算法找到第n/2个数。现在数据集被分成两半，下半部分和上半部分。在下半部分再次找到中点。在其较低的分区上做同样的事情等等......总的来说，这是 O(n) + O(n/2) + O(n/4) + ... = O(n)。
现在，当您必须返回k个最小元素时，搜索最近的x < k，其中x是分区边界。它下面的所有东西都可以返回，并且从下一个分区你必须返回k - x 个数字。由于下一个分区的大小为O(k) ，因此为第k - x个数字运行另一个选择算法将返回其余部分。
于 2013-06-23T14:52:59.890 回答
1
我们可以在线性时间内找到列表的中值并围绕它进行分区。
然后我们可以使用以下算法：维护一个大小为 的缓冲区2k。
每次缓冲区满时，我们都会在它周围找到中值和分区，只保留最低的k元素。
这需要n/k查找中位数和分区步骤，每个步骤都需要O(k)使用传统的快速选择。这种方法只需要O(n)时间。
此外，如果您需要排序的输出。这增加了额外的O(k log k)时间。总的来说，这种方法只需要O(n + k log k)时间和O(k)空间。
于 2013-06-24T11:22:06.633 回答