Top K Frequent Elements: AC by bucket sort

sofkyle · sofkyle · commit ee0408331e90 · 2019-07-21T13:23:40.000+08:00
diff --git a/LeetCodePrj/Java/leetcode/medium/page4/MediumPage4.java b/LeetCodePrj/Java/leetcode/medium/page4/MediumPage4.java
@@ -6,6 +6,6 @@ public class MediumPage4 {
     @Test
     public void testTopKFrequentElements(){
         TopKFrequentElements topKFrequentElements = new TopKFrequentElements();
-        System.out.println(topKFrequentElements.topKFrequent(new int[]{1,2}, 2));
+        System.out.println(topKFrequentElements.topKFrequent(new int[]{-1,-1}, 1));
     }
 }
diff --git a/LeetCodePrj/Java/leetcode/medium/page4/TopKFrequentElements.java b/LeetCodePrj/Java/leetcode/medium/page4/TopKFrequentElements.java
@@ -26,7 +26,7 @@ public List<Integer> topKFrequent(int[] nums, int k) {
 
     private List<Integer> bucketSort(Map<Integer, Integer> frequency) {
         //  get max num
-        int maxNum = 0;
+        int maxNum = Integer.MIN_VALUE;
         for (HashMap.Entry<Integer, Integer> entry : frequency.entrySet()) {
             if (entry.getValue() > maxNum) {
                 maxNum = entry.getValue();
@@ -45,9 +45,11 @@ private List<Integer> bucketSort(Map<Integer, Integer> frequency) {
         }
 
         // sort
-        List<Integer> sortedFrequency = new ArrayList<>(maxNum + 1);
+        List<Integer> sortedFrequency = new ArrayList<>();
         for (int i = maxNum; i > 0; i--) {
-            sortedFrequency.addAll(bucket[i]);
+            if (bucket[i] != null) {
+                sortedFrequency.addAll(bucket[i]);
+            }
         }
 
         return sortedFrequency;

Original file line number	Diff line number	Diff line change
`@@ -6,6 +6,6 @@ public class MediumPage4 {`
`6`	`6`	`@Test`
`7`	`7`	`public void testTopKFrequentElements(){`
`8`	`8`	`TopKFrequentElements topKFrequentElements = new TopKFrequentElements();`
`9`		`- System.out.println(topKFrequentElements.topKFrequent(new int[]{1,2}, 2));`
	`9`	`+ System.out.println(topKFrequentElements.topKFrequent(new int[]{-1,-1}, 1));`
`10`	`10`	`}`
`11`	`11`	`}`