algorithm - 找到 m 个最大的数字

Question

这是Cormen文本中的问题，但我想看看是否还有其他解决方案。

给定一个包含 n 个不同数字的数组，你需要找到数组中最大的 m 个，并且有他们按顺序排列。假设 n 和 m 很大，但增长不同。特别是，你需要下面考虑 m = t*n 的情况，其中 t 是一个小数，比如 0.1，然后可能性m = √n。

书中给出的解决方案提供了3种选择:

1. 对数组进行排序，返回最前面的m段
2. 将数组转换为最大堆并提取 m 个元素
3. 选择第 m 个最大的数，围绕它对数组进行分区，并对较大条目的段进行排序。

这些都是有道理的，而且各有利弊，但是我想知道，还有别的办法吗？它不一定要更好或更快，我只是想看看这是否是更多解决方案的常见问题，或者我们是否仅限于这 3 个选择。

Answer 1

您提到的三种方法的时间复杂度如下。

1. O(n log n)
2. O(n + m log n)
3. O(n + m log m)

因此选项 (3) 在渐近复杂性方面肯定优于其他选项，因为 m <= n。当 m 很小时，(2) 和 (3) 之间的差异很小，几乎没有实际影响。

至于其他的解题方法，你可以有无数种方法，所以这个问题在这方面有点差。以下是我认为实际上简单且高效的另一种方法。

1. 将 n 列表中的前 m 个数字提取到一个数组中，然后对其进行排序。
2. 重复从列表中获取下一个数字并将其插入数组中的正确位置，将所有较小的数字移动一个并推出一个。

不过，如果 m 非常小，我只会这样做。如果您有最大堆实现并且效果很好，则原始列表中的选项 (2) 也非常容易实现。