每日一题 LCR 060. 前 K 个高频元素

LCR 060. 前 K 个高频元素

优先队列轻松解决

struct node{
    int num;
    int cnt;
    node(int n){
        num = n;
        cnt = 0;
    }
    bool operator < (const  node m) const{
        return cnt > m.cnt;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,node*> mp;
        vector<node> vec;
        for(int i=0;i<nums.size();++i){
            if(mp.find(nums[i]) == mp.end()){
                node* temp = new node(nums[i]);

                mp[nums[i]] = temp; 
            }
            mp[nums[i]]->cnt++;
        }
        for(auto [u,v] : mp){
            vec.push_back(*v);
        }
        sort(vec.begin(),vec.end());
        vector<int> ans;
        for(int i=0;i<k;++i){
            ans.push_back(vec[i].num);
        }
        return ans; 
    }
};

使用拉姆达公式更为简介

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(auto num : nums){
            mp[num]++;
        }

        auto cmp = [](pair<int,int> &a, pair<int,int> &b){return a.second > b.second ;} ;

        priority_queue< pair<int,int> ,vector<pair<int,int>> ,decltype(cmp) > minHeap(cmp);

        for(auto [u,v] : mp ){
            minHeap.push({u,v});
            if(minHeap.size() > k){
                minHeap.pop();
            }
        }
        vector<int> ans; 
        while(!minHeap.empty()){
            ans.push_back(minHeap.top().first);
            minHeap.pop();
        }
        return ans;

    }
};