我需要跟踪文本中单词的出现，并且这种情况需要按降序排列 . 我最初使用哈希映射数据结构，但是当我进一步研究时，我发现了“Trie”数据结构 .
我认为“Trie”数据结构非常适合跟踪灵活性和复杂性方面的发生 . 但是还有一个要求，我需要按降序对事件进行排序 . 所以基本上首先遍历“Trie”的搜索 .
实施明智这有点棘手，所以我想知道我是否走在正确的轨道上 . 任何形式的意见都会很棒 . 在这种情况下，最好的数据结构是什么？
注意：排序顺序在出现时下降，因此如果“A”出现5次而“B”出现2次，则排序顺序应为“A”，“B” . 此外，具有相同出现次数的两个单词将按字母顺序排序 .
谢谢
3 回答
如果 words are repeatable 的前缀， trie tree 将是最节省内存的解决方案，遗憾的是仍然是O（N）悲观 . 您需要使用附加信息（单词计数器）来丰富标准的trie-tree类 .
如果您正在寻找悲观的最优解决方案，那么multimap是一个更好的解决方案：
O（1）插入时间（如果您的字母表中有许多字母，则不在特里树中）
O（N）内存和运行时间
但是，您需要对同一事件计数桶中的单词进行排序，如果有多个具有相同出现次数的单词，则排序成为主导操作，并且trie-tree方法与多图方法相同 .
trie的主要属性是合并传入的数据以节省空间，因此如果要使用任何属于任何数据单元的属性，则无法从trie内置属性中受益 . 所以你可以想想如果你想节省空间，使用trie，但是为了获得最常用的词，不知何故你需要使用其他算法（比如一旦收集了数据就遍历trie并准备另一个表） .我的想法很可能是
priority queue与该词的频率，因为关键可能是一个可能的候选人您可以使用三元组，但插入时间很长，但是当您只对前5个最常出现的单词感兴趣时，可以跳过排序算法 .