1636. Sort Array by Increasing Frequency.md

1636. Sort Array by Increasing Frequency

---

the first one in Biweekly Contest 38.

---

Difficulty : Easy

Related Topics : Array、Sort

---

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

---

Solution

• mine
  • Java
    • Runtime: 4 ms, faster than 96.80%, Memory Usage: 39.4 MB, less than 22.76% of Java online submissions

      public int[] frequencySort(int[] nums) {
          int n = nums.length;
          Map<Integer, Integer> map = new HashMap<>();
          for (int num : nums) {
              map.put(num, map.getOrDefault(num, 0) + 1);
          }
          List<Integer>[] list = new List[n + 1];
          for (int num : map.keySet()) {
              int count = map.get(num);
              if (list[count] == null) list[count] = new ArrayList<>();
              list[count].add(num);
          }
          int[] res = new int[n];
          int index = 0;
          for (int i = 0; i <= n && index < n; i++) {
              if (list[i] == null) continue;
              List<Integer> t = list[i];
              Collections.sort(t, (o1, o2) -> o2 - o1);
              for (int j = 0; j < t.size(); j++) {
                  int num = t.get(j);
                  for (int k = 0; k < i; k++) {
                      res[index++] = num;
                  }
              }
          }
          return res;
      }
      

---

• the most votes

• Runtime: 6 ms, faster than 71.23%, Memory Usage: 39 MB, less than 22.76% of Java online submissions

  public int[] frequencySort(int[] nums) {
      var freq = new HashMap<Integer, Integer>();
      for (int n : nums) {
          freq.put(n, 1 + freq.getOrDefault(n, 0));
      }
      var pq = new PriorityQueue<Integer>((i, j) -> freq.get(i) == freq.get(j) ? j - i : freq.get(i) - freq.get(j));
      for (int n : nums) {
          pq.offer(n);
      }
      int i = 0;
      int[] ans = new int[nums.length];
      while(!pq.isEmpty()) {
          ans[i++]= pq.poll();
      }
      return ans;
  }
  

---