add 1636

fishercoder1534 · fishercoder1534 · commit 31e48b6d70dd · 2020-11-01T07:00:45.000-08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1636|[Sort Array by Increasing Frequency](https://leetcode.com/problems/sort-array-by-increasing-frequency/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1636.java) ||Easy|Array, Sort|
 |1630|[Arithmetic Subarrays](https://leetcode.com/problems/arithmetic-subarrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1630.java) ||Medium|Sort|
 |1629|[Slowest Key](https://leetcode.com/problems/slowest-key/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1629.java) ||Easy|Array|
 |1626|[Best Team With No Conflicts](https://leetcode.com/problems/best-team-with-no-conflicts/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1626.java) ||Medium|DP|
diff --git a/src/main/java/com/fishercoder/solutions/_1636.java b/src/main/java/com/fishercoder/solutions/_1636.java
@@ -0,0 +1,42 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.TreeMap;
+
+public class _1636 {
+    public static class Solution1 {
+        public int[] frequencySort(int[] nums) {
+            Map<Integer, Integer> count = new HashMap<>();
+            for (int num : nums) {
+                count.put(num, count.getOrDefault(num, 0) + 1);
+            }
+            TreeMap<Integer, List<Integer>> map = new TreeMap<>();
+            for (int num : count.keySet()) {
+                int freq = count.get(num);
+                if (!map.containsKey(freq)) {
+                    map.put(freq, new ArrayList<>());
+                }
+                List<Integer> list = map.get(freq);
+                list.add(num);
+                map.put(freq, list);
+            }
+            int[] result = new int[nums.length];
+            int i = 0;
+            for (int num : map.keySet()) {
+                List<Integer> list = map.get(num);
+                Collections.sort(list, Collections.reverseOrder());
+                int k = num;
+                for (int j = 0; j < list.size(); j++, k = num) {
+                    while (k-- > 0) {
+                        result[i++] = list.get(j);
+                    }
+                }
+            }
+            return result;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1636Test.java b/src/test/java/com/fishercoder/_1636Test.java
@@ -0,0 +1,30 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1636;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _1636Test {
+    private static _1636.Solution1 solution1;
+    private static int[] nums;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1636.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        nums = new int[]{1, 1, 2, 2, 2, 3};
+        assertArrayEquals(new int[]{3, 1, 1, 2, 2, 2}, solution1.frequencySort(nums));
+    }
+
+    @Test
+    public void test2() {
+        nums = new int[]{-53, -53, 52, 52, 52, 52, -53, -53, 52, -53, 52, 52, 52, -53, 52, 52, -53, 52, -53, 52, -53, 52, 52, 52, 52, 52, 52, 52, 52, 52, -53, 52, -53, 52, -53, 52, 52, 52, -53, -53, 52, -53, 52, 52, 52, 52, -53, -53, -53, -53, -53, 52, 52, -53, 52, -53, 52, 52, 52};
+        assertArrayEquals(new int[]{-53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, -53, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52}, solution1.frequencySort(nums));
+    }
+
+}
