搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。假設目前有一千萬個記錄，這些查詢串的重復度比較高，雖然總數(shù)是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。請你統(tǒng)計最熱門的 10個查詢串，要求使用的內(nèi)存不能超過1G。

　　問題解析：

　　【分析】：要統(tǒng)計最熱門查詢，首先就是要統(tǒng)計每個Query出現(xiàn)的次數(shù)，然后根據(jù)統(tǒng)計結果，找出Top 10。所以我們可以基于這個思路分兩步來設計該算法。下面分別給出這兩步的算法：

　　第一步：Query統(tǒng)計

　　算法一：直接排序法

　　首先我們能想到的算法就是排序了，首先對這個日志里面的所有Query都進行排序，然后再遍歷排好序的Query，統(tǒng)計每個Query出現(xiàn)的次數(shù)了。但是題目中有明確要求，那就是內(nèi)存不能超過1G，一千萬條記錄，每條記錄是225Byte，很顯然要占據(jù)2.55G內(nèi)存，這個條件就不滿足要求了。

　　讓我們回憶一下數(shù)據(jù)結構課程上的內(nèi)容，當數(shù)據(jù)量比較大而且內(nèi)存無法裝下的時候，我們可以采用外排序的方法來進行排序，這里筆者采用歸并排序，是因為歸并排序有一個比較好的時間復雜度O(NlgN)。

　　排完序之后我們再對已經(jīng)有序的Query文件進行遍歷，統(tǒng)計每個Query出現(xiàn)的次數(shù)，再次寫入文件中。

　　綜合分析一下，排序的時間復雜度是O(NlgN)，而遍歷的時間復雜度是O(N)，因此該算法的總體時間復雜度就是O(NlgN)。

　　算法二：Hash Table法

　　在上個方法中，我們采用了排序的辦法來統(tǒng)計每個Query出現(xiàn)的次數(shù)，時間復雜度是NlgN，那么能不能有更好的方法來存儲，而時間復雜度更低呢?

　　題目中說明了，雖然有一千萬個Query，但是由于重復度比較高，因此事實上只有300萬的Query，每個Query255Byte，因此我們可以考慮把他們都放進內(nèi)存中去，而現(xiàn)在只是需要一個合適的數(shù)據(jù)結構，在這里，Hash Table絕對是我們優(yōu)先的選擇，因為Hash Table的查詢速度非常的快，幾乎是O(1)的時間復雜度。

　　那么，我們的算法就有了：維護一個Key為Query字串，Value為該Query出現(xiàn)次數(shù)的HashTable，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并且將Value值設為1;如果該字串在Table中，那么將該字串的計數(shù)加一即可。最終我們在O(N)的時間復雜度內(nèi)完成了對該海量數(shù)據(jù)的處理。

　　本方法相比算法一：在時間復雜度上提高了一個數(shù)量級，但不僅僅是時間復雜度上的優(yōu)化，該方法只需要IO數(shù)據(jù)文件一次，而算法一的IO次數(shù)較多的，因此該算法比算法一在工程上有更好的可操作性。

　　第二步：找出Top 10

　　算法一：排序

　　我想對于排序算法大家都已經(jīng)不陌生了，這里不在贅述，我們要注意的是排序算法的時間復雜度是NlgN，在本題目中，三百萬條記錄，用1G內(nèi)存是可以存下的。

　　算法二：部分排序

　　題目要求是求出Top 10，因此我們沒有必要對所有的Query都進行排序，我們只需要維護一個10個大小的數(shù)組，初始化放入10Query，按照每個Query的統(tǒng)計次數(shù)由大到小排序，然后遍歷這300萬條記錄，每讀一條記錄就和數(shù)組最后一個Query對比，如果小于這個Query，那么繼續(xù)遍歷，否則，將數(shù)組中最后一條數(shù)據(jù)淘汰，加入當前的Query。最后當所有的數(shù)據(jù)都遍歷完畢之后，那么這個數(shù)組中的10個Query便是我們要找的Top10了。

　　不難分析出，這樣的算法的時間復雜度是N*K， 其中K是指top多少。

　　算法三：堆

　　在算法二中，我們已經(jīng)將時間復雜度由NlogN優(yōu)化到NK，不得不說這是一個比較大的改進了，可是有沒有更好的辦法呢?

　　分析一下，在算法二中，每次比較完成之后，需要的操作復雜度都是K，因為要把元素插入到一個線性表之中，而且采用的是順序比較。這里我們注意一下，該數(shù)組是有序的，一次我們每次查找的時候可以采用二分的方法查找，這樣操作的復雜度就降到了logK，可是，隨之而來的問題就是數(shù)據(jù)移動，因為移動數(shù)據(jù)次數(shù)增多了。不過，這個算法還是比算法二有了改進。

　　基于以上的分析，我們想想，有沒有一種既能快速查找，又能快速移動元素的數(shù)據(jù)結構呢?回答是肯定的，那就是堆。借助堆結構，我們可以在log量級的時間內(nèi)查找和調(diào)整/移動。因此到這里，我們的算法可以改進為這樣，維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進行對比。。。

　　那么這樣，這個算法發(fā)時間復雜度就降到了NlogK，和算法而相比，又有了比較大的改進。

　　結語：

　　至此，我們的算法就完全結束了，經(jīng)過步驟一和步驟二的最優(yōu)結合，我們最終的時間復雜度是O(N) + O(N’)logK。如果各位有什么好的算法，歡迎跟帖討論。