前言：算法題中糯彬，有一道經(jīng)典題凭语，那就是尋一堆數(shù)中最大的K個(gè)數(shù)。在此撩扒，我決定總結(jié)一下似扔，做做筆記吨些。
1.應(yīng)用場(chǎng)景有什么？
通常炒辉，海量數(shù)據(jù)搜索最匹配的K個(gè)記錄豪墅，數(shù)據(jù)庫(kù)記錄中獲取最符合某個(gè)特性的K個(gè)記錄，文件中獲取出現(xiàn)文字最多的K篇文章黔寇，以此等等偶器，我們最終都是在對(duì)建立的數(shù)據(jù)模型的求最大K個(gè)數(shù)的求解。
2.解法大全
2.1全排序取K數(shù)法：這個(gè)方法就是用快排或其它排序方法缝裤。將所有數(shù)都排序好屏轰，然后取出最前面或最后的K個(gè)數(shù)。時(shí)間復(fù)雜度O(nlgn+k),適用范圍是數(shù)據(jù)量不大時(shí)憋飞。
2.2快排分治法：采用快排方式霎苗，取一個(gè)基準(zhǔn)數(shù)B，將整個(gè)數(shù)據(jù)集合分成2部分Sa榛做，Sb唁盏。Sa集合中所有數(shù)大于B, Sb集合中所有數(shù)小于B。此時(shí)瘤睹，如果集合Sa個(gè)數(shù)小于K升敲，那么問(wèn)題就變?yōu)樵赟b中求出K-n(Sa)個(gè)最大數(shù)的問(wèn)題；而如果集合Sa個(gè)數(shù)大于K轰传，那么就變成了再在Sa中求最大K個(gè)數(shù)的問(wèn)題驴党。通過(guò)不斷減少數(shù)據(jù)規(guī)模，從而達(dá)到分治目的获茬。這種算法時(shí)間復(fù)雜度和第一種一樣港庄，也只適用于小數(shù)據(jù)量場(chǎng)景。
2.3最小堆方法：取K個(gè)數(shù)構(gòu)成最小堆恕曲，然后掃描所有后續(xù)數(shù)據(jù)鹏氧，與最小堆的堆頂數(shù)比較，如果小于佩谣，則跳過(guò)把还，如果大于，則替換該堆頂元素為比較的數(shù)茸俭，然后調(diào)整堆為新的最小堆吊履。此算法時(shí)間復(fù)雜度為O(n*lgk)。當(dāng)n很大调鬓，K有限大時(shí)艇炎，這個(gè)方法是最好的。因?yàn)椴恍枰阉袛?shù)據(jù)加載到內(nèi)存腾窝，這種算法能處理海量數(shù)據(jù)規(guī)模缀踪。
3.結(jié)論：
采用那種算法居砖，取決于數(shù)據(jù)規(guī)模n和K的大小。對(duì)于海量數(shù)據(jù)驴娃，解法3最優(yōu)奏候。
