在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個(gè)數(shù)，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)，這類(lèi)問(wèn)題通常被稱(chēng)為top K問(wèn)題。

針對(duì)top K類(lèi)問(wèn)題，通常比較好的方案是分治+Trie樹(shù)/hash+小頂堆（就是上面提到的最小堆），即先將數(shù)據(jù)集按照Hash方法分解成多個(gè)小數(shù)據(jù)集，然后使用Trie樹(shù)或者Hash統(tǒng)計(jì)每個(gè)小數(shù)據(jù)集中的query詞頻，之后用小頂堆求出每個(gè)數(shù)據(jù)集中出現(xiàn)頻率最高的前K個(gè)數(shù)，最后在所有top K中求出最終的top K。

方法進(jìn)階：

1、最簡(jiǎn)單的方法就是快排，取topk

2、局部淘汰法。用一個(gè)容器保存前k個(gè)數(shù)，然后將剩余的所有數(shù)字——與容器內(nèi)的最小數(shù)字相比，如果所有后續(xù)的元素都比容器內(nèi)的k個(gè)數(shù)還小，那么容器內(nèi)這k個(gè)數(shù)就是最大k個(gè)數(shù)。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大，則刪掉容器內(nèi)最小元素，并將該元素插入容器，最后遍歷完所有的數(shù)，得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了

3、分治法。將1億個(gè)數(shù)據(jù)分成100份，每份100萬(wàn)個(gè)數(shù)據(jù)，找到每份數(shù)據(jù)中最大的10000個(gè)，最后在剩下的100*10000個(gè)數(shù)據(jù)里面找出最大的10000個(gè)。100萬(wàn)個(gè)數(shù)據(jù)里面查找最大的10000個(gè)數(shù)據(jù)的方法如下：用快速排序的方法，將數(shù)據(jù)分為2堆，如果大的那堆個(gè)數(shù)N大于10000個(gè)，繼續(xù)對(duì)大堆快速排序一次分成2堆，如果大的那堆個(gè)數(shù)N大于10000個(gè)，繼續(xù)對(duì)大堆快速排序一次分成2堆，如果大堆個(gè)數(shù)N小于10000個(gè)，就在小的那堆里面快速排序一次，找第10000-n大的數(shù)字；遞歸以上過(guò)程，就可以找到第1w大的數(shù)。參考上面的找出第1w大數(shù)字，就可以類(lèi)似的方法找到前10000大數(shù)字了。此種方法需要每次的內(nèi)存空間為10^6*4=4MB，一共需要101次這樣的比較。

4、采用最小堆。首先讀入前10000個(gè)數(shù)來(lái)創(chuàng)建大小為10000的最小堆，建堆的時(shí)間復(fù)雜度為O（mlogm）（m為數(shù)組的大小即為10000），然后遍歷后續(xù)的數(shù)字，并于堆頂（最小）數(shù)字進(jìn)行比較。如果比最小的數(shù)小，則繼續(xù)讀取后續(xù)數(shù)字；如果比堆頂數(shù)字大，則替換堆頂元素并重新調(diào)整堆為最小堆。整個(gè)過(guò)程直至1億個(gè)數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有10000個(gè)數(shù)字。該算法的時(shí)間復(fù)雜度為O（nmlogm），空間復(fù)雜度是10000（常數(shù)）。

以下是一些經(jīng)常被提及的該類(lèi)問(wèn)題。

（1）有10000000個(gè)記錄，這些查詢(xún)串的重復(fù)度比較高，如果除去重復(fù)后，不超過(guò)3000000個(gè)。一個(gè)查詢(xún)串的重復(fù)度越高，說(shuō)明查詢(xún)它的用戶(hù)越多，也就是越熱門(mén)。請(qǐng)統(tǒng)計(jì)最熱門(mén)的10個(gè)查詢(xún)串，要求使用的內(nèi)存不能超過(guò)1GB。
（2）有10個(gè)文件，每個(gè)文件1GB，每個(gè)文件的每一行存放的都是用戶(hù)的query，每個(gè)文件的query都可能重復(fù)。按照query的頻度排序。
（3）有一個(gè)1GB大小的文件，里面的每一行是一個(gè)詞，詞的大小不超過(guò)16個(gè)字節(jié)，內(nèi)存限制大小是1MB。返回頻數(shù)最高的100個(gè)詞。
（4）提取某日訪問(wèn)網(wǎng)站次數(shù)最多的那個(gè)IP。
（5）10億個(gè)整數(shù)找出重復(fù)次數(shù)最多的100個(gè)整數(shù)。
（6）搜索的輸入信息是一個(gè)字符串，統(tǒng)計(jì)300萬(wàn)條輸入信息中最熱門(mén)的前10條，每次輸入的一個(gè)字符串為不超過(guò)255B，內(nèi)存使用只有1GB。
（7）有1000萬(wàn)個(gè)身份證號(hào)以及他們對(duì)應(yīng)的數(shù)據(jù)，身份證號(hào)可能重復(fù)，找出出現(xiàn)次數(shù)最多的身份證號(hào)。

最小堆

對(duì)于每個(gè)非葉子節(jié)點(diǎn)的數(shù)值，一定不大于孩子節(jié)點(diǎn)的數(shù)值。這樣可用含有K個(gè)節(jié)點(diǎn)的最小堆來(lái)保存K個(gè)目前的最大值(當(dāng)然根節(jié)點(diǎn)是其中的最小數(shù)值)。每次有數(shù)據(jù)輸入的時(shí)候可以先與根節(jié)點(diǎn)比較。若不大于根節(jié)點(diǎn)，則舍棄；否則用新數(shù)值替換根節(jié)點(diǎn)數(shù)值。并進(jìn)行最小堆的調(diào)整。

Python 小頂堆：

class solution:def topk(self, inputs, k):import heapqif inputs == None or len(inputs) < k or len(inputs) <= 0 or k <= 0:# 注意極限條件的確定return []output = []for number in inputs:if len(output) < k:output.append(number)else:output = heapq.nlargest(k, output)print(output)if number >= output[-1]:output[-1] = numberelse:continuereturn output 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的找出一个字符串中出现次数最多的字_海量数据中找出前k大数（topk问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。