题目描述
给一非空的单词列表,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
注意:
假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。
样例
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
算法
(堆) $O(nlogk)$
题目要求$O(nlogk)$复杂度,所以考虑用堆(优先队列)来做。
- 先用一个哈希表(unordered_map)来统计每个单词出现次数
- 遍历一次哈希表的单词及其频率,把频率的相反数作为堆的排序依据塞进堆中。注意C++默认大顶堆序,我们希望堆顶是k个结果中频率最小的(充当边界线),所以用频率相反数作为排序依据。
- 将堆中元素逆序输出
C++ 代码
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> hash;
typedef pair<int, string> PIS;
priority_queue<PIS> heap;
for (auto word : words) hash[word] ++ ;
for (auto item : hash)
{
PIS t(-item.second, item.first);
if (heap.size() == k && t < heap.top()) heap.pop();
if (heap.size() < k) heap.push(t);
}
vector<string> res(k);
for (int i = k - 1; i >= 0; i -- )
{
res[i] = heap.top().second;
heap.pop();
}
return res;
}
};
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/99712/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相反数省得重载了,妙