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

347. 前 K 个高频元素

自定义结构体排序
解法一

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        for(int i=0;i<nums.size();++i)
        {
            cnt[nums[i]]++;
        }

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

        priority_queue<pair<int,int>,vector<pair<int,int>> , decltype(cmp)> que(cmp);
        vector<int> ans; 
        for(auto [num,numCnt] : cnt )
        {
            que.push({num,numCnt});
            if(que.size() > k)
            {
                que.pop();
            }
        }

        while(!que.empty())
        {
            auto t = que.top();
            int num = t.first;
            que.pop();
            ans.push_back(num);
        }
        return ans;
    }
};

解法二

struct node{
    int num;
    int cnt;
    node()
    {

    }
    bool operator < (const node m)const
    {
        return cnt > m.cnt;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        unordered_map<int,int> mp;
        vector<node> nodes;
        for(int i=0;i<nums.size();++i){
            if(!mp.count(nums[i]))
            {
                mp[nums[i]] = nodes.size();
                node* temp = new node();
                temp->num = nums[i];
                temp->cnt = 0;
                nodes.push_back(*temp);
            }
            int idx = mp[nums[i]];
            nodes[idx].cnt ++;
        }
        sort(nodes.begin(),nodes.end());
        vector<int> ans;
        for(int i=0;i<k;++i){
            ans.push_back(nodes[i].num);
        }
        return ans;
        
    }
};