我在一次采访中被问到这个问题。面试官告诉我假设存在一个函数 getNextWord() 来返回给定文档中的下一个单词。我的任务是设计一个数据结构来实现这个任务，并给出一个算法来构造一个包含所有单词及其频率的列表。
来自 C++ 背景，我的答案是创建一个multimapofstring然后在其中插入所有单词，然后显示count它。然而，后来有人告诉我，以更通用的方式执行此操作。泛指他不希望我使用库功能。另外我猜多图在内部实现为 2-3 树左右，因此为了使多图解决方案具有通用性，我还需要对 2-3 树进行编码。
尽管确实想到了尝试，但在面试中实施一个对我来说是不可能的。所以，我只是想知道是否有更好的方法来实现它？或者有没有办法使用尝试以平滑的方式实现它？
任何基于直方图的算法在这里都是有效的和通用的。这个想法很简单：根据数据构建直方图。直方图的通用接口是Map<String,Integer>
迭代文档一次（使用 nextDoc() 方法），同时保持直方图。
就大 O 表示法而言，此接口的最佳实现可能是使用trie，并在每个叶节点中添加出现计数器。
从 trie 中获取实际(word,number)对将由 trie 上的简单 DFS 完成。
此解决方案为您提供O(n * |S|)时间复杂度，其中 |S| 是字符串的平均大小。
每个单词的插入算法：
每次添加一个新单词时：检查它是否已经存在，如果存在 - 增加计数器，否则 - 将单词添加到字典中，计数器值为 1。
我会尝试实现一个B-Tree（或者非常相似的）来存储所有的单词。因此我可以很容易地找到下一个单词，如果已经有了它并增加节点中的关联计数器。或者只是插入一个新的。
这种情况下的时间复杂度是：O(nlogn)，n所有单词都在哪里计算，并且logn对于这种树来说是一个大哦。
我认为最简单的解决方案是 aa Trie。在这种情况下给出 O(N) （用于插入和获取计数）。只需将计数存储在每个节点的额外空间中。
基本上树中的每个节点都包含 26 个链接到 26 个可能的子节点（每个字母 1 个）+ 1 个计数器（对于在当前节点中终止的词）。只需查看链接以获取特里的图形图像。