关于网站备案,asp.net 网站开发教程,自己开网站做职称论文可以吗,好网站建设公司昆明题目来源#xff1a;力扣
题目描述#xff1a;
给定一个单词列表 words 和一个整数 k #xff0c;返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率#xff0c; 按字典顺序 排序。
示例 1#xff1a;
输入:…题目来源力扣
题目描述
给定一个单词列表 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 次。 代码实现
class Solution {
public:struct Greater{bool operator()(const pairstring,int kv1, const pairstring,int kv2){return kv1.second kv2.second;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int countMap;for(const auto e : words){countMap[e];}vectorpairstring,int KvVec(countMap.begin(),countMap.end());stable_sort(KvVec.begin(),KvVec.end(),Greater());//和sort一样但是stable_sort是稳定的排序vectorstring ret;for(int i0;ik;i){ret.push_back(KvVec[i].first);}return ret;}
};
class Solution {
public:struct Greater{bool operator()(const pairstring,int kv1, const pairstring,int kv2){return kv1.second kv2.second || (kv1.second kv2.second kv1.first kv2.first);//频率大的在前面频率相等的情况下就去比较字典序小的在前面}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int countMap;for(const auto e : words){countMap[e];}vectorpairstring,int KvVec(countMap.begin(),countMap.end());sort(KvVec.begin(),KvVec.end(),Greater());vectorstring ret;for(int i0;ik;i){ret.push_back(KvVec[i].first);}return ret;}
};
这里有两种方法一种是正常使用sort一种是不使用sort
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {mapstring,int countMap;for(const auto e : words){countMap[e];}multimapint,string,greaterint sortMap;//这里依赖map底层实现有些平台可能过不了for(auto kv : countMap){sortMap.insert(make_pair(kv.second,kv.first));}vectorstring v;auto it sortMap.begin();while(k--){v.push_back(it-second);it;}return v;}
};
思路 这道题麻烦的是按照字典序去排列sort是对随机迭代器进行排序的而map是双向迭代器也就是说map是无法使用sort的所以我们在上边倒来倒去的倒数据这道题就是用map统计一下频率然后按频率排序即可这里需要给sort设计一个仿函数让频率大的在前面如果使用原始的sort那么会面临因为sort是不稳定的排序所以要自己加一些条件或者换一个稳定的排序函数比如stable_sort接着我们把前k个放在一个vector里返回即可
除了sort可以排序map也可以再排序我们反过来再搞一个multimapmap会去重排序即可这里需要给map传第三个模板参数这里依赖底层实现有的平台可能不会通过接着一样再把前k个放入vector返回即可
