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;
}
}