[LeetCode] 1636. Sort Array by Increasing Frequency

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

按照频率将数组升序排序。

给你一个整数数组 nums ，请你将数组按照每个值的频率升序排序。如果有多个值的频率相同，请你按照数值本身将它们降序排序。请你返回排序后的数组。

思路就是排序，先用 hashmap 统计每个数字的出现次数，然后对于出现次数相同的数字，我们再按降序排列。这里我先用一个类似451题的 bucket sort 将出现次数相同的数字归在一起。然后当我再次遍历 bucket 的时候，这里需要自己实现一个 comparator 将同一个 bucket 中的元素按降序排列。

时间O(nlogn) - worst case

空间O(n) - bucket

Java实现

 1 class Solution {
 2     public int[] frequencySort(int[] nums) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for (int num : nums) {
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7         List<Integer>[] bucket = new List[101];
 8         for (int key : map.keySet()) {
 9             int freq = map.get(key);
10             if (bucket[freq] == null) {
11                 bucket[freq] = new ArrayList<>();
12             }
13             bucket[freq].add(key);
14         }
15 
16         List<Integer> res = new ArrayList<>();
17         for (int i = 0; i < bucket.length; i++) {
18             if (bucket[i] != null) {
19                 List<Integer> cur = bucket[i];
20                 // cur.sort(Comparator.reverseOrder());
21                 Collections.sort(cur, new Comparator<Integer>() {
22                     public int compare(Integer o1, Integer o2) {
23                         return Integer.compare(o2, o1);
24                     }
25                 });
26                 for (int j = 0; j < cur.size(); j++) {
27                     int count = map.get(cur.get(j));
28                     while (count != 0) {
29                         res.add(cur.get(j));
30                         count--;
31                     }
32                 }
33             }
34         }
35         return res.stream().mapToInt(i -> i).toArray();
36     }
37 }