add a solution for 347

fishercoder1534 · fishercoder1534 · commit 99d368e27166 · 2021-11-03T08:02:19.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_347.java b/src/main/java/com/fishercoder/solutions/_347.java
@@ -7,6 +7,7 @@
 import java.util.Map.Entry;
 import java.util.PriorityQueue;
 import java.util.Queue;
+import java.util.TreeMap;
 
 public class _347 {
 
@@ -74,4 +75,34 @@ public int[] topKFrequent(int[] nums, int k) {
             return arr;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * Use hashtable and heap, it's averaged at 10 ms on Leetocde.
+         */
+        public int[] topKFrequent(int[] nums, int k) {
+            Map<Integer, Integer> map = new HashMap<>();
+            for (int i : nums) {
+                map.put(i, map.getOrDefault(i, 0) + 1);
+            }
+            TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>((a, b) -> b - a);
+            for (int key : map.keySet()) {
+                List<Integer> list = treeMap.getOrDefault(map.get(key), new ArrayList<>());
+                list.add(key);
+                treeMap.put(map.get(key), list);
+            }
+            List<Integer> list = new ArrayList<>();
+            while (!treeMap.isEmpty()) {
+                list.addAll(treeMap.pollFirstEntry().getValue());
+                if (list.size() == k) {
+                    break;
+                }
+            }
+            int[] ans = new int[list.size()];
+            for (int i = 0; i < list.size(); i++) {
+                ans[i] = list.get(i);
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_347Test.java b/src/test/java/com/fishercoder/_347Test.java
@@ -9,13 +9,15 @@
 public class _347Test {
     private static _347.Solution1 solution1;
     private static _347.Solution2 solution2;
+    private static _347.Solution3 solution3;
     private static int[] nums;
     private static int[] expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _347.Solution1();
         solution2 = new _347.Solution2();
+        solution3 = new _347.Solution3();
     }
 
     @Test
@@ -35,6 +37,7 @@ public void test2() {
         nums = new int[]{3, 0, 1, 0};
         expected = new int[]{0, 3};
         assertArrayEquals(expected, solution2.topKFrequent(nums, 2));
+        assertArrayEquals(expected, solution3.topKFrequent(nums, 2));
     }
 
     @Test
