算法-栈和队列:前k个高频元素

2022/2/2 20:12:45

本文主要是介绍算法-栈和队列:前k个高频元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法-栈和队列:前k个高频元素

在一个数组里找出出现频率前k高的元素。

思路解析:

  1. 找出每个元素出现的频率(可以用map);
  2. 按照频率高低来排序(优先级队列);
  3. 找出前k个元素。
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class MyComparison{ //单调队列,队头队尾从大到小
public:
    //定义小顶堆 >
    bool operator()(const pair<int, int>&lhs,const pair<int, int>&rhs){
        return lhs.second > rhs.second;// 注意不要忘记second!!!因为是map所以才重写,如果只有int那么使用greater<int>即可定义小顶堆
    }
};

vector<int> topKeys(vector<int> nums,int k){
    // 1. 找出每个元素出现的频率(可以用map);
    unordered_map<int,int> umap;
    for(int i = 0; i < nums.size(); i++){
        umap[nums[i]]++;
    }
    // 2. 按照频率高低来排序(优先级队列);
    priority_queue<pair<int, int>,vector<pair<int, int>>,MyComparison> priQue;//定义一个优先队列,采用小顶堆
    for(unordered_map<int, int>::iterator it = umap.begin();
        it!= umap.end(); it++){//将map内所有元素都推入优先队列中,如果队列的元素超过k个,那么就弹出队头(队头永远是最小的)
        priQue.push(*it);
        if(priQue.size()>k){
            priQue.pop();
        }
    }
    // 3. 找出前k个元素。
    vector<int> res(k);
    for(int i = k-1; i >= 0; i--){ //小顶堆先弹出的是最小的元素,所以倒序存入res
        res[i] = priQue.top().first;
        priQue.pop();
    }
    return res;
}

int main(){
    vector<int> nums = {2,4,4,-2,-4,3,1,5,5,5,7,8,9,6,8};
    int k;
    while (cin>>k) {
        vector<int> res = topKeys(nums,k);
        for(int i = 0; i < res.size(); i++){
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}


这篇关于算法-栈和队列:前k个高频元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程