输入:正整数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)的方法.
我希望一些信息检索专家可以更多地了解这个问题.