eetcode 347 - top k frequent elements in the array - Java solution - code source: http://buttercola.blogspot.ca/2016/06/leetcode-347-top-k-frequent-elements.html

LC347KMostFrequent1.java

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