347. Top K Frequent Elements

Posted on | Edited on | Views:

LeetCode

HashMap + Heap, Time complexity: O(Nlogk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> count=new HashMap<>();
        for(int i:nums) count.put(i,count.getOrDefault(i,0)+1);
        PriorityQueue<Integer> minHeap=new PriorityQueue<>(
            (o1,o2)->count.get(o1)-count.get(o2)
        );
       
        for(int i:count.keySet()){
            minHeap.offer(i);
            if(minHeap.size()>k) minHeap.poll();
        }
        
        int[] topk=new int[k];
        for(int i=k-1;i>=0;i--) topk[i]=minHeap.poll(); 
        return topk;
    }
}

0%