在 1000 页的书中查找前 3 个出现的单词的算法

Question

<分区>

Answer 1

一个可能更好的解决方案是使用基于 trie 的字典。使用 trie，您可以在最坏情况下执行任务 O(n × N)，其中 N 是单词数，< em>n 是它们的平均长度。与哈希表的区别在于 trie 的复杂性独立于任何哈希函数或书中的词汇。

对于任意输入，没有比 O(n × N) 更好的方法了，因为您必须扫描所有单词。