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 List<Integer> res = new ArrayList<>();
16 for (int i = 0; i < bucket.length; i++) {
17 if (bucket[i] != null) {
18 List<Integer> cur = bucket[i];
19 Collections.sort(cur, new Comparator<Integer>() {
20 public int compare(Integer o1, Integer o2) {
21 return Integer.compare(o2, o1);
22 }
23 });
24 for (int j = 0; j < cur.size(); j++) {
25 int count = map.get(cur.get(j));
26 while (count != 0) {
27 res.add(cur.get(j));
28 count--;
29 }
30 }
31 }
32 }
33 return res.stream().mapToInt(i->i).toArray();
34 }
35 }
相关题目
451. Sort Characters By Frequency
1636. Sort Array by Increasing Frequency