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