Leetcode刷题

Problem 347

Posted by Ruizhi Ma on October 23, 2020

Solution URL

https://leetcode.com/submissions/detail/412462728/

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //ans: https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/
        //Time: O(Nlogk)
        //Space： O(N)
        HashMap<Integer, Integer> map = new HashMap<>();

        //将数组中元素和频率映射到map中
        for(int num: nums){
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else{
                map.put(num, 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()){
            //将k个元素入队
            if(pq.size() < k){
                pq.add(key);
            }else if(map.get(key) > map.get(pq.peek())){//key频率比最小堆堆顶元素频率大，换出来
                pq.remove();
                pq.add(key);
            }
        }

        //取出最小堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        while(!pq.isEmpty()){
            res[idx++] = pq.remove();
        }

        return res;
    }
}