问题是：给定一个字符串列表和一个整数 k，根据频率降序返回前 k 个最常出现的单词。这必须在 O(N) 中完成，其中 N 是字符串列表的长度。
流行的解决方案是将（单词，频率）存储在一个哈希表中，按照频率对哈希表进行排序，输出前k个单词。然而，这不是 O(N)，因为按频率排序需要 O(NlgN)。
我想知道是否确实存在 O(N) 解决方案。我考虑过快速选择在哪里获得第 k 个最常出现的单词并对剩余的频率进行排序，但是当 k 是 N 时，这将是 O(N + klgk)，它仍然是 O(NlgN)。
问问题
1437 次
2 回答
1
是的，它确实存在。没有必要对这些对进行实际排序。可以在 O(n) 中找到第 k 个元素（这是一种众所周知的算法）。那么所有大于或等于第k个元素的元素都是top元素。
于 2014-08-09T17:03:32.023 回答
1
是的，有一个 O(n) 解决方案。
您可以根据需要更改以 O(n) 复杂度运行的著名 SELECT 算法（该算法的目的是从 N 个元素中找到第 K 个最小的元素）。
然后你只需选择与算法返回的元素“大于或等于”的元素。
您可以在以下位置找到更多详细信息：SELECT 算法
于 2014-08-09T19:08:18.387 回答