java是否有一个O（N）解决方案来获取列表中最常出现的前k个字符串<string>？
问题是：给定一个字符串列表和一个整数k，根据频率降序返回前k个最常出现的单词。这必须在O（N）中完成，其中N是字符串列表的长度
流行的解决方案是将（单词、频率）存储在哈希表中，按频率对哈希表排序，然后输出前k个单词。然而，这不是O（N），因为按频率排序需要O（NlgN）
我想知道O（N）解是否真的存在。我曾经考虑过快速选择，在那里你可以得到第k个出现频率最高的单词，并对剩余的频率进行排序，但那将是O（N+klgk），当k是N时，它仍然是O（NlgN）
# 1 楼答案
是的，有一个O（n）解
您可以根据您的需要更改以O（n）复杂度运行的著名选择算法 （该算法的目的是从N个元素中找出第K个最小元素）
然后，您只需选择与算法返回的元素“大于或等于”的元素
有关更多详细信息，请访问：SELECT algorithm
# 2 楼答案
是的，它确实存在。没有必要对这些对进行实际排序。可以在O（n）中找到第k个元素（这是一个众所周知的算法）。然后，大于或等于第k个元素的所有元素都是顶部元素