347. 前 K 个高频元素

[Ni-Guvara]

class Mycom
{
    public:
        const bool operator()(const pair<int,int> & lhs,const pair<int,int> &rhs)
        {
            return lhs.second > rhs.second;
        }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        vector<int> ret; // 返回数据
        // 将各个数字的频率统计

        int len = nums.size();
        unordered_map<int,int> cnt;

        for(int idx = 0; idx < len ;idx++)
            cnt[nums[idx]]++;

        // 建立小顶对

        priority_queue<pair<int,int>,vector<pair<int,int>>,Mycom> que;

        for(unordered_map<int,int>::iterator it = cnt.begin();it!= cnt.end();it++)
        {
            que.push(*it);
            if(que.size() > k)
                que.pop();
        }

        // 结果装入
        while(!que.empty())
        {
            pair<int,int> p = que.top();
            ret.push_back(p.first);

            que.pop();
        }                      

        return ret;  
    }
};

[rocksc30]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        // 最小堆保存频率最高的元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

        for (Integer key : map.keySet()) {
            if (pq.size() < k){
                pq.add(key);
            }else if(map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }
        int[] ret = new int[k];

        for (int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }

        return ret;
    }

}