TOP K使用思路是什么

TOP K使用思路是什么，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

TOP K

通用思路：

1、使用Hash取模的方法將大文件劃分成若干小文件；

2、使用HashMap或者字典樹（trie樹）對小文件進行詞頻統計；

3、對小文件按照詞頻進行排序（堆排序等），取每個小文件的前N個；

4、將小文件的結果歸并排序，再對歸并后的文件取前N個。

有1億個浮點數，如果找出期中最大的10000個？

對于第三部，首先讀入前10000個數來創建大小為10000的最小堆，建堆的時間復雜度為O（mlogm）（m為數組的大小即為10000），然后遍歷后續的數字，并于堆頂（最小）數字進行比較。如果比最小的數小，則繼續讀取后續數字；如果比堆頂數字大，則替換堆頂元素并重新調整堆為最小堆。整個過程直至1億個數全部遍歷完為止。然后按照中序遍歷的方式輸出當前堆中的所有10000個數字。

有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。

順序讀文件中，對于每個詞x，取hash(x)%5000，然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右。
如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小文件的大小都不超過1M。 對每個小文件，統計每個文件中出現的詞以及相應的頻率（可以采用trie樹/hash_map等），并取出出現頻率最大的100個詞（可以用含100個結點的最小堆），并把100個詞及相應的頻率存入文件，這樣又得到了5000個文件。下一步就是把這5000個文件進行歸并（類似與歸并排序）的過程了。

給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？

申請512MB的內存，一個bit位代表一個unsigned int值。讀入40億個數，設置相應的bit位，讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在。

已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位整數可以表示的最大十進制數值為99999999。如果每個數字對應于位圖中一個bit位，那么存儲8位整數大約需要99MB。因為1B=8bit，所以99Mbit折合成內存為99/8=12.375MB的內存，即可以只用12.375MB的內存表示所有的8位數電話號碼的內容。

給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？

如果使用布隆過濾器，那么問題就很好辦了，4G的內存足以容納300多億的bit，所以足夠處理了，先將a文件中的url都放入布隆過濾器，之后遍歷b文件，對每個url都詢問布隆過濾器看其是否已經存在，如果存在，則此條URL輸入結果文件。

看完上述內容，你們掌握TOP K使用思路是什么的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！