Top K问题
程序员文章站
2024-03-15 21:52:00
...
-
出现频率Top k的元素
LeetCode 347
给定一个非空整数数组,返回出现最多的k个元素
输入:[1,1,1,2,2,3] k=2
输出:[1,2]
/* 思路:对于此类求top k的问题,都可以用堆排序来实现。map容器和set容器是按照key值来进行排序的,且是按照从小到大排序。而priority_queue是优先级队列,它的底层是大顶堆。因此可以将元素的出现次数放在pair的key,元素的值放在pair的value,中间使用map来进行过度。 */ class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { map<int, int> temp; priority_queue<pair<int, int>> heap; vector<int> res; for(int i = 0; i < nums.size(); ++i) temp[nums[i]]++; map<int, int>::iterator it = temp.begin(); while(it != temp.end()) { heap.push(make_pair(it->second, it->first)); it++; } for(int i = 0; i < k; ++i) { res.push_back(heap.top().second); heap.pop(); } return res; } };
-
出现频率Top k的单词
LeetCode 692
对于出现频率top k的单词,当几个单词出现频率一样时,按照字典顺序排列。而优先级队列底层大顶堆,不会按照字典顺序排列,需要我们对其比较函数进行重新定义。
//第一个参数为元素类型,第二从参数是来承载底层数据结构堆的容器,第三个参数是一个比较类 priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap; //cmp的实现 struct cmp { bool operator()(pair<string, int> a, pair<string, int> b) { if(a.second == b.second) return a.first > b.first; else return a.second < b.second; } };
对于priority_queue来说,默认是大顶堆,也可以通过修改第三个参数,来将其改为小顶堆
priority_queue<pair<string, int>, vector<pair<string, int>>, greater<pair<string,int>> > q; //小顶堆 priority_queue<pair<string, int>, vector<pair<string, int>>, less<pair<string,int>> > q; //大顶堆
输入:[“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出:[“i”, “love”]
/* 思路:先将字符串和其对应的出现次数存在map中,然后将其存在priority_queue中,并重新定义其比较函数。最终取前k个即可。 */ struct cmp { bool operator()(pair<string, int> a, pair<string, int> b) { if(a.second == b.second) return a.first > b.first; else return a.second < b.second; } }; class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> temp; priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap; vector<string> res; for(int i = 0; i < words.size(); ++i) temp[words[i]]++; map<string, int>::iterator it = temp.begin(); while(it != temp.end()) { heap.push(make_pair(it->first, it->second)); it++; } for(int i = 0; i < k; ++i) { res.push_back(heap.top().first); heap.pop(); } return res; } };
上一篇: for循环打印一个九九乘法表
下一篇: 7-5 堆中的路径 -PTA