在O(n)中返回文档中10个最常用的单词

Question

如何设计一个算法,可以在O(n)时间内返回文档中10个最常用的单词？如果可以使用额外的空间.

我可以解析并将单词放在带有计数的哈希映射中.但接下来我必须对值进行排序以获得最常见的值.此外,我必须有一个映射btw值 - >键,由于值可能重复,无法维护.

那我怎么解决这个问题呢？

Answer 1

这是一个简单的算法:

• 通过文档一次读一个字.上)
• 使用每个单词构建一个HashTable.上)
  • 使用单词作为键.O(1)
  • 使用您将此单词视为值的次数.O(1)
  • (例如,如果要将密钥添加到哈希表中,则值为1;如果已在哈希表中具有密钥,则将其关联值增加1)O(1)
• 创建一对大小为10的数组(即字符串字[10]/int count [10],或使用<Pair>),使用此对来跟踪下一步中10个最常用的单词及其字数.O(1)
• 迭代完成的HashTable一次:O(n)
  • 如果当前字的字数高于数组对中的条目,则替换该特定条目并将所有内容向下移位1个插槽.O(1)
• 输出这对数组.O(1)

O(n)运行时.

O(n)存储HashTable +数组

(旁注:您可以将HashTable视为字典:存储密钥的方法:密钥唯一的值对.技术上HashMaps意味着异步访问,而HashTable意味着同步.)