[LeetCode] Problem 347 - Top K Frequent Elements

Posted on | In ,

Given a non-empty array of integers, return the k most frequent elements.

Example

No.1

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

No.2

Input: nums = [1], k = 1

Output: [1]

Note

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
        @Override
        public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
            return o1.getValue() - o2.getValue();
        }
    });

    for (int num : nums)
        map.put(num, map.getOrDefault(num, 0) + 1);

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (minHeap.size() < k)
            minHeap.offer(entry);
        else if (entry.getValue() > minHeap.peek().getValue()) {
            minHeap.poll();
            minHeap.offer(entry);
        }
    }

    while (!minHeap.isEmpty())
        result.add(minHeap.poll().getKey());

    return result;
}