LeetCode 1636. 按照频率将数组升序排序
题目描述
题意分析
按每个数在整个数组中的出现次数升序排序；出现次数相同时，数值较大的排在前面。排序只改变顺序，所有重复元素都需要保留。
解法：频次统计 + 自定义排序
核心思路
[!blue]
先完整扫描数组，用freq[v]记录每个值的总出现次数。排序过程中这个表保持不变，因此同一个数无论移动到哪里，都使用相同的排序依据。比较两个值
a、b时，先看freq[a]与freq[b]，次数较小者在前；仅当次数相等时，再让较大的数值在前。这相当于按“频次升序、数值降序”两个固定关键字排序，完整表达了题目的优先级。排序对象是数组中的全部元素，所以重复次数不会丢失。两个元素若在两级比较中都相等，它们的数值也相同，交换先后不会改变结果，因此不要求稳定排序。Java 先转为
Integer[]以使用自定义比较器，排好后写回int[]；Go 直接排序原切片。
解题步骤
- 统计所有值的频次。
- Java 创建装箱数组，Go 直接使用原切片。
- 比较频次升序，平局比较数值降序。
- 返回重排后的数组。
代码实现
class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : nums) {
freq.put(v, freq.getOrDefault(v, 0) + 1);
}
// 使用完整频次进行排序，主键频次升序，平局按数值降序。
Integer[] arr = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
arr[i] = nums[i];
}
Arrays.sort(
arr,
(a, b) -> {
int fa = freq.get(a);
int fb = freq.get(b);
if (fa != fb) {
return Integer.compare(fa, fb);
}
return Integer.compare(b, a);
});
for (int i = 0; i < nums.length; i++) {
nums[i] = arr[i];
}
return nums;
}
}
import "sort"
func frequencySort(nums []int) []int {
freq := make(map[int]int)
for _, v := range nums {
freq[v]++
}
// 使用完整频次进行排序，主键频次升序，平局按数值降序。
sort.Slice(nums, func(i, j int) bool {
a, b := nums[i], nums[j]
if freq[a] != freq[b] {
return freq[a] < freq[b]
}
return a > b
})
return nums
}
复杂度分析
- 时间复杂度：期望 $O(n\log(n+1))$，哈希统计线性，排序占主导。
- 空间复杂度：Java 为 $O(n)$，包含装箱数组和排序辅助空间；Go 为 $O(u+\log n)$，包含频次表与排序调用栈，$u$ 为不同数值个数。两份实现都会重排输入数组。
关键点总结
[!green]
- 先比频次，再处理数值平局。
- 比较期间频次保持不变，不能边比较边增加计数。
- 排序重排全部元素，不做去重。
易错点总结
[!yellow]
- 次关键字也升序：同频段的数值顺序相反。
- 只按频次排序：无法保证平局时数值降序。
- 给 int[] 直接传比较器：Java 没有这一 Arrays.sort 重载。
- Go 比较器使用小于等于：相同元素应返回 false，保持严格比较。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 451. 根据字符出现频率排序 | 中等 | 同样按全局出现频次排序，本题频次升序且同频值降序，原题按字符频次降序。 |
| 1356. 根据数字二进制下 1 的数目排序 | 简单 | 两题都是多关键字排序，但原题第一键是数值内部的位1数量，本题是数组中的出现次数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！