前言：算法題中，有一道經(jīng)典題，那就是尋一堆數(shù)中最大的K個數(shù)。在此，我決定總結(jié)一下，做做筆記。

1.應(yīng)用場景有什么？

通常，海量數(shù)據(jù)搜索最匹配的K個記錄，數(shù)據(jù)庫記錄中獲取最符合某個特性的K個記錄，文件中獲取出現(xiàn)文字最多的K篇文章，以此等等，我們最終都是在對建立的數(shù)據(jù)模型的求最大K個數(shù)的求解。

2.解法大全

2.1全排序取K數(shù)法：這個方法就是用快排或其它排序方法。將所有數(shù)都排序好，然后取出最前面或最后的K個數(shù)。時間復(fù)雜度O(nlgn+k),適用范圍是數(shù)據(jù)量不大時。

2.2快排分治法：采用快排方式，取一個基準(zhǔn)數(shù)B，將整個數(shù)據(jù)集合分成2部分Sa，Sb。Sa集合中所有數(shù)大于B, Sb集合中所有數(shù)小于B。此時，如果集合Sa個數(shù)小于K，那么問題就變?yōu)樵赟b中求出K-n(Sa)個最大數(shù)的問題；而如果集合Sa個數(shù)大于K，那么就變成了再在Sa中求最大K個數(shù)的問題。通過不斷減少數(shù)據(jù)規(guī)模，從而達(dá)到分治目的。這種算法時間復(fù)雜度和第一種一樣，也只適用于小數(shù)據(jù)量場景。

2.3最小堆方法：取K個數(shù)構(gòu)成最小堆，然后掃描所有后續(xù)數(shù)據(jù)，與最小堆的堆頂數(shù)比較，如果小于，則跳過，如果大于，則替換該堆頂元素為比較的數(shù)，然后調(diào)整堆為新的最小堆。此算法時間復(fù)雜度為O(n*lgk)。當(dāng)n很大，K有限大時，這個方法是最好的。因為不需要把所有數(shù)據(jù)加載到內(nèi)存，這種算法能處理海量數(shù)據(jù)規(guī)模。

3.結(jié)論：

采用那種算法，取決于數(shù)據(jù)規(guī)模n和K的大小。對于海量數(shù)據(jù)，解法3最優(yōu)。