一个文本文件,有上亿行甚至十亿行,每行一个词,要求统计出其中出现最频繁的前 10 个词,请给
出思路和时间复杂度的分析。
提示:因为文件比较大,无法一次读入内存,故可以用 hash 并求模,将文件分解为多个小文件,对于
单个文件利用 hash_map 统计出每个文件中 10 个最常出现的词。然后再进行归并处理,找出最终的 10 个
最常出现的词。

也可以用 trie 树统计每个词出现的次数,时间复杂度是 O(n x le)(le 表示单词的平准长度)。然后找
出出现最频繁的前 10 个词,可用堆来实现,前面的题中已经讲到了,时间复杂度是 O(n x lg10)。所以总的
时间复杂度,是 O(n x le)与 O(n x lg10)中较大的那一个。

Last modification:August 26th, 2020 at 03:25 pm
如果觉得我的文章对你有用,请随意赞赏