滕州网站建设 助企网络,潍坊滨海开发区建设局网站,2022可以用手机看的,新软件推广平台1. 题目
给一非空的单词列表#xff0c;返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。 如果不同的单词有相同出现频率#xff0c;按字母顺序排序。
示例 1#xff1a;
输入: [i, love, leetcode, 返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。 如果不同的单词有相同出现频率按字母顺序排序。
示例 1
输入: [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 次。注意
假定 k 总为有效值 1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。扩展练习
尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。来源力扣LeetCode 链接https://leetcode-cn.com/problems/top-k-frequent-words 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 优先队列
struct cmp
{bool operator()(const pairstring,int a, const pairstring,int b){if(a.second b.second)return a.first b.first;//字典序大的在上面return a.second b.second;//数量小的在上面}
};
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {unordered_mapstring,int m;for(string s : words)m[s];//计数priority_queuepairstring,int,vectorpairstring,int,cmp q;for(auto mi : m){if(q.size() k)//维持大小为k的堆q.push(mi);else//满了{if(mi.second q.top().second)//数量多进去{q.pop();q.push(mi);}else if(mi.second q.top().second mi.first q.top().first){ //数量一样字典序小进去q.pop();q.push(mi);}}}vectorstring ans;while(!q.empty()){ans.push_back(q.top().first);q.pop();}reverse(ans.begin(), ans.end());return ans;}
};16 ms 11.4 MB
