Modified Top K Frequent Elements.java

varunu28 · varunu28 · commit 9fd78fb1bca8 · 2020-05-28T16:24:35.000-05:00
diff --git a/Medium/Top K Frequent Elements.java b/Medium/Top K Frequent Elements.java
@@ -1,49 +1,24 @@
 class Solution {
-
-    public List<Integer> topKFrequent(int[] nums, int k) {
-        Map<Integer, Integer> map = new HashMap<>();
-
-        for (int i=0;i<nums.length;i++) {
-            if (map.containsKey(nums[i])) {
-                map.put(nums[i], map.get(nums[i])+1);
-            }
-            else {
-                map.put(nums[i], 1);
-            }
-        }
-        
-        Map<Integer, Integer> sortedMap = sortByValue(map);
-        
-        List<Integer> ans = new ArrayList<>();
-        int c = 0;
-        
-        for (Map.Entry<Integer,Integer> entry : sortedMap.entrySet()) {
-            if (c == k) break;
-            ans.add(entry.getKey());
-            
-            c++;
-        }
-        
-        return ans;
+  public int[] topKFrequent(int[] nums, int k) {
+    Map<Integer, Integer> map = new HashMap<>();
+    for (int num : nums) {
+      map.put(num, map.getOrDefault(num, 0) + 1);
     }
-    
-    private Map<Integer, Integer> sortByValue(Map<Integer, Integer> unsortMap) {
-
-        List<Map.Entry<Integer, Integer>> list =
-                new LinkedList<Map.Entry<Integer, Integer>>(unsortMap.entrySet());
-
-        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
-            public int compare(Map.Entry<Integer, Integer> o1,
-                               Map.Entry<Integer, Integer> o2) {
-                return (o2.getValue()).compareTo(o1.getValue());
-            }
-        });
-
-        Map<Integer, Integer> sortedMap = new LinkedHashMap<Integer, Integer>();
-        for (Map.Entry<Integer, Integer> entry : list) {
-            sortedMap.put(entry.getKey(), entry.getValue());
-        }
-
-        return sortedMap;
+    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
+      public int compare(Integer p1, Integer p2) {
+        return map.get(p1) - map.get(p2);
+      }
+    });
+    for (Integer key : map.keySet()) {
+      pq.add(key);
+      if (pq.size() > k) {
+        pq.poll();
+      }
     }
+    int[] ans = new int[k];
+    for (int i = 0; i < k; i++) {
+      ans[i] = pq.poll();
+    }
+    return ans;
+  }
 }
