一. 立刻就能想到的解法既然是要前 K 大的數(shù),，那么最直接的當(dāng)然就是排序了，通過如快排等效率較高的排序算法,，可以在平均 O（nlogn）的時間復(fù)雜度找到結(jié)果,。 這種方式在數(shù)據(jù)量不大的時候簡單可行，但固然不是最優(yōu)的方法,。 二. O(n) 時間復(fù)雜度的方法剛剛提到了快排,，熟悉算法題的小伙伴應(yīng)該知道，快排的 partition 劃分思想可以用于計算某個位置的數(shù)值等問題,，例如用來計算中位數(shù),；顯然，也適用于計算 TopK 問題 每次經(jīng)過劃分,，如果中間值等于 K ,，那么其左邊的數(shù)就是 Top K 的數(shù)據(jù),； 當(dāng)然，如果不等于,，只要遞歸處理左邊或者右邊的數(shù)即可 該方法的時間復(fù)雜度是 O(n) ,，簡單分析就是第一次劃分時遍歷數(shù)組需要花費(fèi) n，而往后每一次都折半（當(dāng)然不是準(zhǔn)確地折半）,，粗略地計算就是 n + n/2 + n/4 +... \< 2n,，因此顯然時間復(fù)雜度是 O(n) 對比第一個方法顯然快了不少，隨著數(shù)據(jù)量的增大,，兩個方法的時間差距會越來越大 缺點(diǎn) 雖然時間復(fù)雜度是 O(n) ,，但是缺點(diǎn)也很明顯，最主要的就是內(nèi)存問題,，在海量數(shù)據(jù)的情況下,，我們很有可能沒辦法一次性將數(shù)據(jù)全部加載入內(nèi)存，這個時候這個方法就無法完成使命了 還有一點(diǎn)就是這種思路需要我們修改輸入的數(shù)組,，這也是值得考慮的一點(diǎn) 三. 利用分布式思想處理海量數(shù)據(jù)面對海量數(shù)據(jù),，我們就可以放分布式的方向去思考了 我們可以將數(shù)據(jù)分散在多臺機(jī)器中，然后每臺機(jī)器并行計算各自的 TopK 數(shù)據(jù),，最后匯總,，再計算得到最終的 TopK 數(shù)據(jù) 這種數(shù)據(jù)分片的分布式思想在面試中非常值得一提，在實際項目中也十分常見 四. 利用最經(jīng)典的方法,，一臺機(jī)器也能處理海量數(shù)據(jù)其實提到 Top K 問題,，最經(jīng)典的解法還是利用堆。 維護(hù)一個大小為 K 的小頂堆,，依次將數(shù)據(jù)放入堆中,，當(dāng)堆的大小滿了的時候，只需要將堆頂元素與下一個數(shù)比較：如果大于堆頂元素,，則將當(dāng)前的堆頂元素拋棄,，并將該元素插入堆中。遍歷完全部數(shù)據(jù),，Top K 的元素也自然都在堆里面了,。 當(dāng)然，如果是求前 K 個最小的數(shù),，只需要改為大頂堆即可 將數(shù)據(jù)插入堆 95 大于 20,，進(jìn)行替換 95 下沉，維持小頂堆 對于海量數(shù)據(jù),，我們不需要一次性將全部數(shù)據(jù)取出來,，可以一次只取一部分，因為我們只需要將數(shù)據(jù)一個個拿來與堆頂比較,。 另外還有一個優(yōu)勢就是對于動態(tài)數(shù)組,，我們可以一直都維護(hù)一個 K 大小的小頂堆,，當(dāng)有數(shù)據(jù)被添加到集合中時，我們就直接拿它與堆頂?shù)脑貙Ρ?。這樣,，無論任何時候需要查詢當(dāng)前的前 K 大數(shù)據(jù)，我們都可以里立刻返回給他,。 整個操作中,，遍歷數(shù)組需要 O(n) 的時間復(fù)雜度，一次堆化操作需要 O(logK),，加起來就是 O(nlogK) 的復(fù)雜度,，換個角度來看，如果 K 遠(yuǎn)小于 n 的話,， O(nlogK) 其實就接近于 O(n) 了,，甚至?xí)?，因此也是十分高效的?/p> 最后,，對于 Java，我們可以直接使用優(yōu)先隊列 PriorityQueue 來實現(xiàn)一個小頂堆,，這里給個代碼： Language TXT public List<Integer> solutionByHeap(int[] input, int k) { List<Integer> list = new ArrayList<>(); if (k > input.length || k == 0) { return list; } Queue<Integer> queue = new PriorityQueue<>(); for (int num : input) { if (queue.size() < k) { queue.add(num); } else if (queue.peek() < num){ queue.poll(); queue.add(num); } } while (k-- > 0) { list.add(queue.poll()); } return list; }
|
|
|
