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

Question

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

我可以使用 count 解析单词并将其放入 HashMap 中。但接下来我必须对值进行排序以获得最常见的值。此外，我还必须有一个映射 btw values -> Key 不能维护，因为值可能会重复。

那我该如何解决呢？

Answer 1

这是一个简单的算法:

• 一次阅读文档中的一个单词。 O(n)
• 使用每个单词构建一个哈希表。 O(n)
  • 使用单词作为关键字。 O(1)
  • 使用您看到该词的次数作为值。 O(1)
  • (例如，如果您要将键添加到哈希表，则值为 1；如果哈希表中已有该键，则将其关联值增加 1)O(1)<
• 创建一对大小为 10 的数组(即 String words[10]/int count[10]，或使用 )，使用这对来跟踪 10 个最常出现的单词及其单词计数下一步。 O(1)
• 遍历完成的 HashTable 一次:O(n)
  • 如果当前单词的单词计数高于数组对中的一个条目，则替换该特定条目并将所有内容向下移动 1 个槽位。 O(1)
• 输出一对数组。 O(1)

O(n) 运行时间。

O(n) 哈希表 + 数组的存储

(旁注:您可以将 HashTable 视为字典:一种存储键值对的方法，其中键是唯一的。从技术上讲，HashMap 意味着异步访问，而 HashTable 意味着同步访问。)