双语教学示范课程建设项目网站,濮阳网站关键词,wordpress分库技术,软件app大全免费692. 前K个高频单词 描述示例解题思路及事项思路一思路二 描述
给定一个单词列表 words 和一个整数 k #xff0c;返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率#xff0c; 按字典顺序 排序
示例
示例1
输… 692. 前K个高频单词 描述示例解题思路及事项思路一思路二 描述
给定一个单词列表 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 次。
解题思路及事项
思路一
遇到这样的题我们一般思路肯定就是TOP-K问题这样想当然没有问题但是我们这里数据没那么多用到这里属于杀鸡焉用牛刀不过我们可以试一试等下在讲别的思路。
不管是那个思路首先这是一对一的关系我们肯定要先用到map,统计不同字符串出现的次数。
TOP-K在于建大堆和小堆的问题这道题建议建大堆。我们现在已经学了C因此可以使用priority_queue它默认就是建大堆 然后把前K个元素拿出来就好了
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {mapstring,int mp;for(auto str:words){mp[str];}vectorstring ret;//这里我们建一个大堆priority_queuepairstring,int py;auto itmp.begin();while(it ! mp.end()){py.push(*it);it;}while(k--){ret.push_back(py.top().first);py.pop();}return ret;}
};这是根据我们的思路写出来的代码 但是结果不对难道我们思路出现了问题这道题不应该这样解 其实并不是这样的思路是对的但是问题就在于priority_queue第三个参数仿函数的比较出现了问题。 因为它比较的是pair对象。而pair的相关比较函数我们可以看看到底是怎么比的 可以看到pair是先比较first如果first相等在比较second。 但是我们的pair第一个参数是string第二个参数是int。 这于我们想要优先比较int就不对因此我们自己写一个仿函数。
class Solution {
public:templateclass Tstruct Less{bool operator()(const pairstring,int l,const pairstring,int r){return l.second r.second;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int mp;for(auto str:words){mp[str];}vectorstring ret;//这里我们建一个大堆priority_queuepairstring,int,vectorpairstring,int,Lesspairstring,int py;auto itmp.begin();while(it ! mp.end()){py.push(*it);it;}while(k--){ret.push_back(py.top().first);py.pop();}return ret;}
};运行结果还是出现了问题。经过分析可能是建大堆出现了问题我们打印一下看看是不是这个问题。 经过对比发现它们出现次数都是6次就是建立大堆谁在上面谁在下面出现了问题。
注意看到我们的题目要求不同单词出现相同频率按 字典顺序 排序 而我们在写自己的仿函数的时候只考虑了出现次数不同的情况而没有考虑这个情况。
class Solution {
public:templateclass Tstruct Less{bool operator()(const pairstring,int l,const pairstring,int r){//出现次数相同就按 字典顺序 排序return l.second r.second || (l.second r.second l.first r.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int mp;for(auto str:words){mp[str];}// for(auto e: mp)// {// coute.first:e.secondendl;// }vectorstring ret;//这里我们建一个大堆priority_queuepairstring,int,vectorpairstring,int,Lesspairstring,int py;auto itmp.begin();while(it ! mp.end()){py.push(*it);it;}while(k--){ret.push_back(py.top().first);py.pop();}return ret; }
};思路二
刚才说过使用堆来对少的数据排序杀鸡焉用牛刀了。现在想一想我用map建立一对一的关系之后我给它排序一下不就好了吗反正有算法库给我提供的sort函数。那来试一试
注意sort底层使用的快速排序结构是线性结构而map并不是线性结构而是树形结构因此要把map里的数据放在vector才能使用sort。 sort默认是升序第一个版本是按照operator比较的第二个是按照comp比较的也就是说我们给它提供一个仿函数按照自己的想法比较。 由TOP-K我们就知道如果直接让pair对比会有问题所以我们选第二种。
class Solution {
public:struct Compare{bool operator()(const pairstring,int l,const pairstring,int r){return l.second r.second || (l.second r.second l.first r.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int mp;for(auto str:words){mp[str];}vectorstring ret;vectorpairstring,int v;for(auto e:mp){v.push_back(e);}//这个Compare我们是按照降序进行判断的sort(v.begin(),v.end(),Compare());for(int i0;ik;i){ret.push_back(v[i].first);}return ret;}
};这样也能解决问题不过这样的sort并不能保持稳定性需要我自己手动控制才能保持稳定性以达到相同次数按 字典顺序 排序。 下面介绍一种稳定的排序算法。 stable_sort可以保持排序的稳定性。 i 在 love的前面出现次数相同i 依旧在 love前面。
class Solution {
public:struct Compare{bool operator()(const pairstring,int l,const pairstring,int r){return l.second r.second ;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int mp;for(auto str:words){mp[str];}vectorstring ret;vectorpairstring,int v;for(auto e:mp){v.push_back(e);}//这个Compare我们是按照降序进行判断的//sort(v.begin(),v.end(),Compare());stable_sort(v.begin(),v.end(),Compare());for(int i0;ik;i){ret.push_back(v[i].first);}return ret;}
};
