algorithm - 部分选择排序与归并排序查找 "k largest in array"

Question

我想知道我的思路是否正确。

我正在准备面试(作为一名大学生)，我遇到的其中一个问题是找到数组中 K 个最大的数字。

我的第一个想法是只使用部分选择排序(例如，从第一个元素开始扫描数组，并为看到的最低元素及其索引保留两个变量，并在数组末尾与该索引交换并继续这样做直到我们交换了 K 个元素并返回该数组中前 K 个元素的副本)。但是，这需要 O(K*n) 时间。如果我简单地使用像 Mergesort 这样的高效排序方法对数组进行排序，则只需 O(n*log(n)) 时间即可对整个数组进行排序并返回 K 个最大的数字。

在采访中讨论这两种方法是否足够好(比较输入的 log(n) 和 K，并使用两者中较小的一个来计算最大的 K)，还是可以安全地假设我' m 期望为这个问题给出 O(n) 的解决方案？

Answer 1

存在一个O(n) algorithm for finding the k'th smallest element ，一旦你有了那个元素，你就可以简单地浏览列表并收集适当的元素。它基于 Quicksort，但其工作原理背后的原因相当复杂……还有一个更简单的变体，可能 将在 O(n) 中运行。 My answer to another question包含对此的简短讨论。