輸入：正整數(shù)K和大文本。實(shí)際上，文本可以被視為單詞序列。因此，我們不必?fù)?dān)心如何將其分解為單詞序列。輸出：文本中最常見(jiàn)的K字。我的想法是這樣的。使用哈希表來(lái)記錄所有單詞的頻率，同時(shí)遍歷整個(gè)單詞序列。在此階段，鍵是“字”，值是“字頻”。這需要O（n）時(shí)間。對(duì)（字，字 - 頻率）對(duì)進(jìn)行排序; 關(guān)鍵是“字頻”。這需要使用正常排序算法的O（n * lg（n））時(shí)間。排序后，我們只取第一個(gè)K字。這需要O（K）時(shí)間?？偠灾倳r(shí)間是O（n + n lg（n）+ K），因?yàn)镵肯定小于N，所以它實(shí)際上是O（n lg（n））。我們可以改善這一點(diǎn)。實(shí)際上，我們只想要前K個(gè)詞。換句話說(shuō)，頻率對(duì)我們來(lái)說(shuō)并不重要。因此，我們可以使用“部分堆排序”。對(duì)于步驟2）和3），我們不僅僅進(jìn)行排序。相反，我們改變它2'）構(gòu)建一堆（word，word-frequency）對(duì)，以“word-frequency”為關(guān)鍵。構(gòu)建堆需要花費(fèi)O（n）時(shí)間;3'）從堆中提取前K個(gè)單詞。每次提取為O（lg（n））。所以，總時(shí)間是O（k * lg（n））?？偠灾?，該解決方案花費(fèi)時(shí)間O（n + k * lg（n））。這只是我的想法。我還沒(méi)有找到改進(jìn)步驟1）的方法。我希望一些信息檢索專家可以對(duì)這個(gè)問(wèn)題有所了解。