| 1 | class Solution { |
| 2 | public List<Integer> topKFrequent(int[] nums, int k) { |
| 3 | // build hash map : character and how often it appears |
| 4 | HashMap<Integer, Integer> count = new HashMap(); |
| 5 | for (int n: nums) { |
| 6 | count.put(n, count.getOrDefault(n, 0) + 1); |
| 7 | } |
| 8 | |
| 9 | // init heap 'the less frequent element first' |
| 10 | PriorityQueue<Integer> heap = |
| 11 | new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2)); |
| 12 | |
| 13 | // keep k top frequent elements in the heap |
| 14 | for (int n: count.keySet()) { |
| 15 | heap.add(n); |
| 16 | if (heap.size() > k) |
| 17 | heap.poll(); |
| 18 | } |
| 19 | |
| 20 | // build output list |
| 21 | List<Integer> top_k = new LinkedList(); |
| 22 | while (!heap.isEmpty()) |
| 23 | top_k.add(heap.poll()); |
| 24 | Collections.reverse(top_k); |
| 25 | return top_k; |
| 26 | } |
| 27 | } |