免费网站建设模版云盘,自己做网站语言构建服务器,厦门百度推广开户,网店推广的目的有哪些题目#xff1a;给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
分析#xff1a;首先我们需要计算数组中元素出现的频率#xff0c;前几篇文章讲解了哈希表的应用#xff0c;所以这里我们很容易想到用…题目给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
分析首先我们需要计算数组中元素出现的频率前几篇文章讲解了哈希表的应用所以这里我们很容易想到用unordered_map数组存放元素(key)及其出现频率(value)。然后我们需要根据value值进行排序map的常用排序是根据key值进行的排序。所以我们根据value进行排序需要将map转换为vector结构然后对整个数组进行排序。但是如果我们采用优先级队列可以只维护k个有序的序列。
然后我们要考虑使用大顶堆还是小顶堆。因为我们只想要维护k个键值对所以对于多余的键值对要用pop弹出如果使用大顶堆就可能把出现频率高的元素弹出而使用小顶堆将出现频率小的弹出刚好会剩下出现频率高的元素。最后由于小顶堆小的在前所以在放入vectorint result数组时要逆序放。
注优先级队列如果不指定第三个参数默认是大顶堆所以我们可以采用仿函数函数对象来实现小顶堆定义。具体代码
class Solution {
public:class Mycomparison {public:bool operator() (const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {unordered_mapint, int map;for(int i 0; i nums.size(); i) {map[nums[i]];}priority_queuepairint, int, vectorpairint, int, Mycomparison pri_que;for(unordered_mapint, int::iterator it map.begin(); it ! map.end(); it) {pri_que.push(*it);if(pri_que.size() k) {pri_que.pop();}}vectorint result(k);for(int i k - 1; i 0; i--) {result[i] pri_que.top().first;pri_que.pop();}return result;}
};
