class Solution {
public:
  //对vector排序的谓词，前面加static
    static bool compare(pair<int, int> map1, pair<int, int> map2) 
    {
        return map1.second > map2.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> num_map; //map统计出现的次数
        vector<pair<int ,int >> buf; //缓存vector，用作排序
        vector<int> result;
        for( auto i:nums)
        {
            num_map[i]++; //统计出现的次数
        }
        for ( auto it : num_map) //将map中的数据存到vector中，用pair的形式
        {
            buf.push_back(make_pair(it.first, it.second)); 
            // cout<<it.first<<' '<<it.second<<endl;
        }
        sort(buf.begin(), buf.end(),compare);    //排序，按照value的大小排序
        for(int i = 0 ; i<k ;i++)
        {
            result.push_back(buf[i].first);   //前k个值为结果
        }
        return result;
    }
};

class Solution {
public:
    // 小顶堆的比较函数
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> num_map;
        vector<int> result;
        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison>  pri_que;
        for( auto i:nums)
        {
            num_map[i]++;
        }
        for ( auto it : num_map)
        {
            pri_que.push(it);
            if (pri_que.size() > k)// 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
            { 
                pri_que.pop();
            }
        }
        for(int i = k - 1; i >= 0; i--) //小顶堆，先出的小，倒着装入数组
        {
            result.push_back( pri_que.top().first);
            pri_que.pop();
        }
        return result;
    }
};

class Solution {
public:
    static bool cmp(const pair<int,int>&a, const pair<int,int>&b )
    {
        return a.second > b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> my_map;
        vector<int> resulte;
        for(int i=0 ; i<nums.size() ;i++)
        {
            my_map[nums[i]]++;
        }
        vector<pair<int,int>> tmp(my_map.begin(),my_map.end()); 
        sort(tmp.begin(),tmp.end(),cmp);
        for(int i=0 ; i<k ;i++)
        {
            resulte.push_back(tmp[i].first);
        }
        return resulte;
    }
};