寻找m最大数字

Question

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

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

书中给出的解决方案提供3个选项：

1. 排序阵列并返回顶部米长的段
2. 阵列转换为最大堆并提取m个元素
3. 选择第m个最大的数字，对该数组进行分区，然后对较大条目的分段进行排序。

这些都有道理，他们都有自己的优点和缺点，但我想知道，有没有另一种方式来做到这一点？它不一定要更好或更快，我只是好奇，看看这是更多解决方案的常见问题，还是仅限于这3种选择。

Answer 1

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

1. 为O（n log n）的
2. O（N + M日志N）
3. O（N + M登入）

所以选项（3）肯定比更好其他在渐近复杂性方面，因为m < = n。当m很小时，（2）和（3）之间的差异非常小，实际影响不大。

至于解决问题的其他方法，可以有无数种方法，所以在这方面这个问题有点不好。我能想到的另一种方法是简单实用，如下所示。

1. 从列表中的前m个数字中提取数组并排序。
2. 反复从您的列表中获取下一个数字，并将其插入阵列中的正确位置，将所有较少的数字移过一个并将其推出。

我只会这样做，如果米是非常小虽然。如果您拥有最大堆实现并且工作效果很好，那么从原始列表中选择（2）也非常容易实现。

Answer 2

一种不同的方法。

取前m个数字，并将它们变成最小堆。如果数组的值超过顶端m的最小值，则通过该数组运行，然后提取最小值并插入新值。当您到达数组的末尾时，您可以将这些元素提取到数组中并将其反转。

该版本的最差情况下的性能是O(n log(m))将其置于第一种和第二种效率方法之间。

平均情况更有趣。平均而言，只有O(m log(n/m))的元素将通过第一次比较测试，每次都会产生O(log(m))工作，因此您会得到O(n + m log(n/m) log(m))的工作，这将其置于第二种和第三种方法之间。 但是如果n比m大很多个数量级然后O(n)件支配，并且在第三种方法中的中值选择具有比这种方法中的每个元素比较差的常量，所以在这种情况下，这实际上是最快的！