可能重复：
在大词序列中查找前 K 个频繁词的最有效方法
在 1000 页的书中查找出现次数最多的 3 个单词的算法。有比使用哈希表更好的解决方案吗？
问问题
4140 次
6 回答
3
一个可能更好的解决方案是使用基于 trie 的字典。使用 trie，您可以在最坏情况 O( n × N ) 时间内执行任务，其中N是单词的数量，n是它们的平均长度。与哈希表的不同之处在于，trie 的复杂性与任何哈希函数或书中的词汇无关。
对于任意输入，没有比 O( n × N ) 更好的方法了，因为您必须扫描所有单词。
于 2012-04-17T23:14:22.773 回答
3
奇怪的是，每个人都专注于浏览单词列表而忘记了主要问题——取k个最频繁的项目。实际上，哈希映射足以计算出现次数，但是这种实现仍然需要排序，这实际上是 O(n*logn) （最好的情况下）。
因此，哈希映射实现需要 1 次通过来计算单词（不保证 O(n)）和 O(n*logn) 来对其进行排序。这里提到的尝试可能是更好的计数解决方案，但排序仍然是问题。再一次，1遍+排序。
你真正需要的是一个堆，即基于树的数据结构，它使最大（最低）元素接近根。堆的简单实现（例如二进制堆）需要 O(logn) 时间来插入新元素，需要 O(1) 时间才能获得最高元素，因此生成的算法将需要 O(n*logn) 并且只有 1 pass。更复杂的实现（例如Fibonacci heap）需要平均 O(1) 时间进行插入，因此生成的算法需要 O(n) 时间，这比任何建议的解决方案都要好。
于 2012-04-18T01:55:43.927 回答
1
您将不得不逐字浏览所有页面才能获得准确的答案。
因此，也使用哈希表接口来存储指向链表节点的指针的链表实现会做得很好。
您需要链表动态增长，哈希表需要快速访问所需的正确节点，以便更新计数。
于 2012-04-17T23:15:02.213 回答
-1
维基百科是这样说的：
“对于某些字符串处理应用程序，例如拼写检查，哈希表的效率可能低于尝试、有限自动机或 Judy 数组。此外，如果每个键都由足够少的位数表示，那么，而不是哈希表表，可以直接将键用作值数组的索引。请注意，在这种情况下没有冲突。
我也会猜到一个哈希树。
于 2012-04-17T23:14:47.000 回答
-1
一个简单的方法是使用Dictionary<string, int>(.net) orHashTable并在扫描整本书时计算每个单词的出现次数。
于 2012-04-17T23:09:06.390 回答
-1
于 2012-04-18T08:42:25.623 回答