Top問題常見具體場景問法、算法及時間空間複雜度分析

（1）有10000000個記錄，這些查詢串的重複度比較高，如果除去重複後，不超過3000000個。一個查詢串的重複度越高，說明查詢它的使用者越多，也就是越熱門。請統計最熱門的10個查詢串，要求使用的記憶體不能超過1GB。

（2）有10個檔案，每個檔案1GB，每個檔案的每一行存放的都是使用者的query，每個檔案的query都可能重複。按照query的頻度排序。

（3）有一個1GB大小的檔案，裡面的每一行是一個詞，詞的大小不超過16個位元組，記憶體限制大小是1MB。傳回頻數最高的100個詞。

（4）提取某日通路網站次數最多的那個IP。

（5）10億個整數找出重複次數最多的100個整數。

（6）搜尋的輸入資訊是一個字元串，統計300萬條輸入資訊中最熱門的前10條，每次輸入的一個字元串為不超過255B，記憶體使用隻有1GB。

（7）有1000萬個身份證号以及他們對應的資料，身份證号可能重複，找出出現次數最多的身份證号。

此處不再贅述其他排序方法，最優方法無疑是堆排序。

堆排序是通過維護大頂堆或者小頂堆來實作的。

堆排序法來解決N個數（非常大）中的TopK的思路是：

1、先随機取出N個數中的K個數，将這N個數構造為小頂堆，那麼堆頂的數肯定就是這K個數中最小的數了。

2、然後再将剩下的N-K個數與堆頂進行比較，如果大于堆頂，那麼說明該數有機會成為TopK，就更新堆頂為該數。

3、此時由于小頂堆的性質可能被破壞，就還需要調整堆；否則說明這個數最多隻能成為Top K+1 th，丢棄不用管它。

4、然後就将下一個數與目前堆頂的數作比較，根據大小關系如上面所述方法進行操作，直到N-K個數都周遊完，

5、此時堆中的K個數就是TopK。

複雜度分析：

根據堆排序的複雜度，不難得出，在該方法中，首先需要對K個元素進行建堆，時間複雜度為O(K);然後對剩下的N-K個數對堆頂進行比較及更新，最好情況下當然是都不需要調整了，那麼時間複雜度就隻是周遊這N-K個數的O(N-K)，這樣總體的時間複雜度就是O(N)，而在最壞情況下，N-K個數都需要更新堆頂，每次調整堆的時間複雜度為logK，是以此時時間複雜度就是NlogK了，總的時間複雜度就是O(K)+O(NlogK)≈O(NlogK)。

空間複雜度是O(1)。

值得注意的是，堆排序法提前隻需讀入K個資料即可，可以實作來一個資料更新一次，能夠很好的實作資料動态讀入并找出TopK。