java - 是否有O(N)解决方案来获取List <String>中最常见的k个字符串？

This question already has answers here:

The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
（19个答案）
问题是：给定一个字符串列表和一个整数k，根据频率按降序返回前k个最常出现的单词必须执行O（N），其中N是字符串列表的长度。
流行的解决方案是将（word，frequency）存储在哈希表中，按频率对哈希表进行排序，并输出前k个单词。但这不是o（n），因为按频率排序需要o（nlgn）。
我想知道O（n）解是否真的存在。我已经考虑过快速选择在哪里得到第k个出现频率最高的单词，并对剩余的频率进行排序，但那将是O（N+klgk），当k为N时，仍然是O（NlgN）。

最佳答案

是的，确实存在。不需要真正地对这对进行排序。在o（n）中可以找到第k个元素（这是一个众所周知的算法）。那么所有大于或等于第k个元素的元素都是顶部元素。

关于java - 是否有O(N)解决方案来获取List <String>中最常见的k个字符串？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25220945/