我想知道我的思路是否正确。
我正在准备面试(作为一名大学生)，我遇到的问题之一是找到数组中最大的 K 个数字。
我的第一个想法是只使用部分选择排序(例如，从第一个元素扫描数组，并为所见的最低元素及其索引保留两个变量，并与数组末尾的该索引交换，然后继续这样做直到我们交换了 K 个元素并返回该数组中前 K 个元素的副本)。
然而，这需要 O(K*n) 时间。如果我只是使用像 Mergesort 这样的高效排序方法对数组进行排序，那么只需要 O(n*log(n)) 时间即可对整个数组进行排序并返回 K 个最大的数字。
在面试期间讨论这两种方法是否足够好(比较输入的 log(n) 和 K 并使用两者中较小的一个来计算 K 最大)，或者可以安全地假设我'我期望给出这个问题的 O(n) 解决方案吗？
最佳答案
存在 O(n) algorithm for finding the k'th smallest element ，一旦获得该元素，您就可以简单地扫描列表并收集适当的元素。它基于快速排序，但其工作原理背后的原因相当复杂……还有一个更简单的变体，可能将在 O(n) 中运行。 My answer to another question包含对此的简短讨论。
关于algorithm - 部分选择排序与合并排序查找 "k largest in array"，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26981819/