arrays - 打印数组中的 K 个最小数字(不是第 k 个最小的)

Question

我正在接受采访。

采访者:你有一个数组，你必须找到该数组中的 k 个最小元素，你还必须高效吗？
例如:[2,1,4,5,0] 如果输入为 3，则输出将为 0,1,2。

我:我将获取 k 个变量并遍历数组的每个元素，并将所有不同的 k 个最小值存储在 k 个不同的变量中。

采访者:如果您有数百万个数据并且必须找到 10000 个最小的变量怎么办？

我:是的，取 10000 个变量实际上是不可能的。因此，我将对数百万数据迭代冒泡排序 10,000 次。

采访者:不，好吧，下一个问题!

So, I want to know what is the correct method for finding k smallest number in an array, specially when k is some very large number?

Answer 1

首先，我们需要找到数组中第 k 个最小的元素。这可以通过任何 selection algorithm 来完成.

In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic.

然后我们需要像快速排序算法一样进行分区操作。分区对数组重新排序，以便所有值小于第 k 个最小元素的元素排在它之前，而所有值大于第 k 个最小元素的元素排在它之后。分区的复杂度是O(n)。

选择算法的一个非常简单的实现是 Quickselect算法(包括分区)，类似于快速排序。在一般情况下，算法的复杂度为 O(n)。

在最坏的情况下，有更复杂的方法可以在 O(n) 中找到第 k 个最小元素(第 k 阶统计量)，例如 Median of median algorithm .但我认为 Quickselect 足以回答面试问题。