效率最高的可能是使用链接到最大堆的Patricia trie.每次你读一个单词,它都在trie上,然后去堆.如果它不在trie中,则将其密钥设置在堆中.findincrease-keyadd
有了Fibonacci堆,increase-key是O(1).
一个不太合理的解决方案是使用a Map<String, Integer>,每次遇到一个单词时添加计数,然后entrySet()根据计数对其进行自定义排序以获得前50名.
如果O(N log N)排序是不可接受的,请使用选择算法查找前50位O(N).
哪种技术更好取决于你所要求的(即评论这是一个[algorithm]问题,而不是一个[java]问题非常有说服力).
在Map<String, Integer>随后选择算法是最实用的,但帕特里夏特里解决方案清楚地击败它在单独的空间利用率(因为共同的前缀不是冗余存储).