Leetcode-347-Top K Frequent Elements

Top K Frequent Elements

leetcode: https://leetcode.com/problems/top-k-frequent-elements/

Description:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Idea:

**solution **

**Step1: **First use hashmap to record each element and their corresponding frequency.

Step2: create the priority queue and use comparator to build the ascending queue.(the Max heap), so the first element of the queue is the biggest.

Step3: add all element’s and corrsponding frequency to the queue.

Step4: get kth elements of the queue from the first element.

Code:

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        //use map to record the element and corresponding frequence
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        //max heap
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        //store elements to queue
        for (int key : map.keySet())
            queue.add(new int[]{key, map.get(key)});

        //Take the largest k elements in the heap
        int index=0;
        //because the queue is ascending order, so just poll kth elements.
        while(k-->0){
            result[index++] = queue.poll()[0];
        }   
        return result;
    }
}