给定一个文件,尽可能有效地找到十个最常出现的单词

Question

这显然是一个面试问题(在一系列面试问题中找到它),但即使它不是很酷.

我们被告知要在所有复杂性措施上有效地做到这一点.我想创建一个HashMap,将单词映射到它们的频率.这将是时间和空间复杂度的O(n),但由于可能有很多单词,我们不能假设我们可以将所有内容存储在内存中.

我必须补充一点,问题中没有任何内容说这些单词不能存储在内存中,但是如果是这样的话呢？如果情况并非如此,那么这个问题似乎并不具有挑战性.

Answer 1

优化我自己的时间:

sort file | uniq -c | sort -nr | head -10

可能接着是awk '{print $2}'消除计数.

Answer 2

我认为trie数据结构是一种选择.

在trie中,您可以在每个节点中记录字数,表示从根到当前节点的路径上由字符组成的字的频率.

设置trie的时间复杂度是O(Ln)~O(n)(其中L是最长单词中的字符数,我们可以将其视为常数).为了找到前10个单词,我们可以遍历trie,这也需要花费O(n).所以需要O(n)才能解决这个问题.

Answer 3

您可以进行时间/空间权衡，通过计算每次在数据的线性传递中遇到某个单词时出现的次数来获取O(n^2)时间和（内存）空间。O(1)如果计数高于迄今为止找到的前 10 个，则保留该单词和计数，否则忽略它。