Leetcode: 347. Top K Frequent Elements

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

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.

Solution:
Use a min-heap.

Code (Java):

?

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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

public class Solution {     public List<Integer> topKFrequent(int[] nums, int k) {         List<Integer> result = new ArrayList<>();         if (nums == null || nums.length == 0) {             return result;         }                   // step 1: count the freq of each word         Map<Integer, Integer> map = new HashMap<>();         for (int num : nums) {             if (map.containsKey(num)) {                 int freq = map.get(num);                 map.put(num, freq + 1);             } else {                 map.put(num, 1);             }         }                   // step 2: use a min-heap to get the top k frequencies.         PriorityQueue<Pair> pq = new PriorityQueue<>(new MyPQComparator());         int count = 0;         for (int word : map.keySet()) {             int freq = map.get(word);             Pair pair = new Pair(freq, word);             if (count < k) {                 pq.offer(pair);             } else if (pair.freq > pq.peek().freq) {                 pq.poll();                 pq.offer(pair);             }             count++;         }                   // step 3: output the result         for (Pair pair : pq) {             result.add(pair.word);         }                   return result;     }           private class MyPQComparator implements Comparator<Pair> {         @Override         public int compare(Pair a, Pair b) {             return a.freq - b.freq;         }     } }   class Pair {     int word;     int freq;           Pair(int freq, int word) {         this.word = word;         this.freq = freq;     } }