尋找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)件支配，並且在第三種方法中的中值選擇具有比這種方法中的每個元素比較差的常量，所以在這種情況下，這實際上是最快的！