题目描述
给定非空单词列表,返回k个最常见的元素。
您的答案应按频率从最高到最低排序。如果两个单词的频率相同,则字母顺序较低的单词首先出现。
例1:
输入: [“i”,“love”,“leetcode”,“i”,“love”,“coding”],k = 2
输出: [“i”,“love”]
说明: “我”和“爱” “是最常用的两个词。
请注意,由于字母顺序较低,“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。
注意:
你可以假设ķ始终是有效的,1个≤ ķ独特元素的数量≤。
输入字仅包含小写字母。
跟进:
尝试在O(n log k)时间和O(n)额外空间中解决它。
样例
typedef pair<string,int>Pll;
bool cmp(Pll a,Pll b)//比较函数要放在类外
{
return a.second>b.second||a.second==b.second&&a.first<b.first;//排序顺序
}
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int>hash;
vector<string>res;
vector<Pll>p;
for(int i=0;i<words.size();i++)
{
hash[words[i]]++;//哈希存储字符串
}
for(auto it=hash.begin();it!=hash.end();it++)//end不包含具体指,是结束的标志
p.push_back({it->first,it->second});
sort(p.begin(),p.end(),cmp);
for(int i=0;i<k;i++)
res.push_back(p[i].first);
return res;
}
};
这是nlogn的解法