问题是:给定一个字符串列表和一个整数 k，根据频率按降序返回前 k 个最常出现的单词。这必须完成 O(N)，其中 N 是字符串列表的长度。
流行的解决方案是将(单词，频率)存储在哈希表中，按频率对哈希表进行排序，并输出前 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/