LeetCode - Algorithms - 347. Top K Frequent Elements

Problem

347. Top K Frequent Elements

Java

Priority queues with comparators

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] a = new int[k];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        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);
            }
        }

        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<Map.Entry<Integer, Integer>>(k, Map.Entry.<Integer, Integer>comparingByValue().reversed());
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            maxHeap.offer(e);
        }

        while (k > 0) {
            a[--k] = maxHeap.poll().getKey();
        }

        return a;        
    }
}

Submission Detail

  • 21 / 21 test cases passed.
  • Runtime: 11 ms, faster than 37.93% of Java online submissions for Top K Frequent Elements.
  • Memory Usage: 41.2 MB, less than 96.44% of Java online submissions for Top K Frequent Elements.