题目描述
给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。
样例
示例 1:
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 "i" 在 "love" 之前。
示例 2:
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。
算法(hsah + 小根堆)
用pair排序可以兼顾字典序排序,第一个int关键字相等,会继续按第二个关键字string字典序排序。
使用小根堆可以保持堆里面一直保持k个元素,之后统一输出即可。
大根堆 + 次数取负数 => 小根堆 直接用小根堆无法处理字典序问题
越接近大根堆顶的原本值是最小的,由于取负数,变为最大,同时可以满足即使int值相同,string字典序小的也更靠近大根堆顶。 之后倒序输出即是答案。
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);
heap.push(t);
if (heap.size() > k) heap.pop();
}
vector<string> res(k);
for (int i = k - 1; i >= 0; i --)
{
res[i] = heap.top().second;
heap.pop();
}
return res;
}
};