12. [Technical Interview] Top K Frequent Elements

You will use a max heap to place the most occurrences of a number at the top of the queue and going down in count.

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

import java.util.*; public class HelloWorld{ public static void main(String []args){ int[] testIntArray = {1, 1, 1, 2, 2, 3}; List<Integer> result = topKFrequent(testIntArray, 3); Iterator it = result.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } public static List<Integer> topKFrequent(int[] nums, int k) { // count the frequency of each number in nums and add // them to the map Map<Integer, Integer> counterMap = new HashMap<Integer, Integer>(); for (int num : nums) { int countValue = counterMap.getOrDefault(num, 0); counterMap.put(num, countValue + 1); } PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> b.getValue()-a.getValue()); for (Map.Entry<Integer, Integer> entry : counterMap.entrySet()) { pq.offer(entry); } Iterator it = pq.iterator(); while (it.hasNext()) { System.out.println ( "Value: "+ it.next()); } List<Integer> result = new LinkedList<Integer>(); int counter = 0; while (counter < k) { if (result == null) System.out.println ("bad result"); if (pq == null) System.out.println ("bad pq"); result.add(pq.poll().getKey()); counter++; } return result; } }