prepare阵列中的线性时间来得到k最小元素为O（K） [英] Prepare array in linear time to find k smallest elements in O(k)

问题描述

这是我在网上找到了一个有趣的问题。由于包含数组 N 号（有没有关于它们的信息），我们应该pre-过程中的线性时间序列，以便我们可以返回<$ C $ ç> K 中的 O（K） 的时候，当我们被赋予了许多 1＆LT; = K＆LT; = N

This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 <= k <= n

我一直在讨论这个问题的一些朋友，但没有人能找到一个解决方案;任何帮助，将AP preciated！

I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!

推荐答案

对于pre-处理步骤，我们将使用分区为基础的选择相同的数据集多次。

For the pre-processing step, we will use the partition-based selection several times on the same data set.

找到π/ 2 的-th数的算法..现在数据集被划分为两个半，下部和上部。在下半部找到再次middlepoint。在其下的分区做同样的事情等等...总的来说，这是O（n）+ O（N / 2）+ O（N / 4）+ ... = O（N）。

Find the n/2-th number with the algorithm.. now the dataset is partitioned into two half, lower and upper. On the lower half find again the middlepoint. On its lower partition do the same thing and so on... Overall this is O(n) + O(n/2) + O(n/4) + ... = O(n).

现在，当你有返回的 K 的最小元素，寻找最近的 X 的＆LT; K 的，其中的 X 的是一个分区的边界。它下面的一切都可以返回，并从下一个分区，你必须返回的 K - X 的数字。由于下一个分区的大小的 O（K）的，用于运行其它的选择算法的 K - X 的日数将返回剩下的

Now when you have to return the k smallest elements, search for the nearest x < k, where x is a partition boundary. Everything below it can be returned, and from the next partition you have to return k - x numbers. Since the next partition's size is O(k), running another selection algorithm for the k - x th number will return the rest.

这篇关于prepare阵列中的线性时间来得到k最小元素为O（K）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！