LeetCode 1636. 按照频率将数组升序排序

约 9 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 华为
标签
数组 哈希表 排序
目录

题目描述

✅ 1636. 按照频率将数组升序排序

题意分析

给定一个整数数组，要按「出现次数从小到大」重新排列它；如果两个数的出现次数相同，则按「数值从大到小」排列。返回重排后的数组。

注意排序的对象仍然是原数组里的每一个元素，而不是去重后的值。出现三次的数在结果里仍然出现三次，且这三份必然连续地挤在一起——因为它们的频次和数值都相同，任何满足规则的排列都会把它们排在相邻位置。

两条规则的方向是相反的：频次升序、数值降序。这种一升一降的组合是本题最容易写错的地方，比较器里两段的减法方向必须一正一反。

数组长度上限 100，元素值域是 [-100, 100]。规模极小，任何 $O(n \log n)$ 甚至 $O(n^2)$ 的写法都能过，所以考点不在效率，而在能否准确地把双关键字规则翻译成比较器。

值域有限（只有 201 种可能取值）是个可选的优化信号：频次统计可以用偏移后的定长数组代替哈希表。不过用哈希表更通用，也更贴近面试时的默认写法。

边界上，所有元素互不相同时频次全为 1，退化成单纯的降序排列；所有元素相同时任何顺序都满足规则。

解法：频次统计 + 自定义排序

核心思路

一个想当然的做法是先按值排序，再按频次做一次排序。这在使用稳定排序时能凑效，但把两个关键字拆成两趟处理既绕又依赖排序算法的稳定性，一旦换成不稳定排序（Java 对基本类型数组用的就是不稳定的双轴快排）结果就不可控。

瓶颈在于把「双关键字」当成了两次单关键字操作。正确的做法是在一次排序里同时表达两个关键字：主关键字先比，相等时才看次关键字。

要比较频次，就必须先知道每个值出现了多少次。所以第一步是扫一遍数组建立「值 → 频次」的映射。这一步是 $O(n)$ 的，之后每次比较都能 $O(1)$ 查到频次。

第二步是带比较器的排序。先比较两个元素的频次 fa 与 fb，频次小的排前；频次相同时反向比较数值，让较大的数排前。Java 用 Integer.compare(fa, fb) 与 Integer.compare(b, a)，Go 则分别判断 freq[a] < freq[b] 与 a > b。

这里有一个 Java 特有的实现细节：Arrays.sort 只有在数组元素是对象类型时才接受比较器，对 int[] 这样的基本类型数组没有带比较器的重载。所以必须先把 int[] 装箱成 Integer[]，排完再拆箱写回。Go 则没有这个问题，sort.Slice 可以直接对 []int 原地排序。

不变量是：排序完成后，对结果中任意相邻两个元素 x 和 y（x 在前），要么 freq[x] < freq[y]，要么 freq[x] == freq[y] 且 x >= y。这条性质由比较器的全序性保证，也正是题目要求的全部内容。

排序只重排原数组，不改变元素及其出现次数；比较器又让任意相邻元素都满足上述次序。因此输出既保留原多重集合，又符合题目的两级排序规则。

解题步骤

  • 先遍历数组，用哈希表统计每个值的出现次数。用 getOrDefault(v, 0) + 1 累加，避免为「首次出现」单独写分支。
  • 频次必须一次性统计完再开始排序。比较器会以不可预测的顺序访问元素，如果边排边统计，拿到的频次就是不完整的中间值。
  • Java 里把 int[] 逐个拷贝进 Integer[]。这不是多余的动作——Arrays.sort(int[], Comparator) 这个重载并不存在，不装箱就无法使用自定义比较器。
  • 比较器先比频次：fa != fb 时返回 Integer.compare(fa, fb)，实现频次升序。使用标准比较函数，不把正确性建立在减法不会溢出的当前约束上。
  • 频次相同时返回 Integer.compare(b, a)，参数方向与上一段相反，实现数值降序。
  • 排序结束后把 Integer[] 的内容写回 int[] 并返回。题目要求返回 int[]，直接返回装箱数组类型不匹配。
  • Go 版本用 sort.Slice 直接对 []int 原地排序，比较函数返回布尔值：频次不等时返回 freq[a] < freq[b]，相等时返回 a > b。布尔语义下同样是一个「小于」一个「大于」，方向相反。
  • 注意 Go 的 sort.Slice 是不稳定排序，但本题不受影响——频次与数值都相同的元素本来就是同一个数，谁在前谁在后没有区别。

以 nums = [2, 3, 1, 3, 2] 走一遍：统计得到频次表 {2: 2, 3: 2, 1: 1}。开始排序：元素 1 的频次是 1，最小，排在最前。元素 2 与元素 3 的频次都是 2，进入次关键字比较，按数值降序，3 排在 2 前面。所以最终顺序是 [1, 3, 3, 2, 2]。可以验证：频次序列是 1、2、2、2、2，非递减；频次相同的段内数值是 3、3、2、2，非递增。再看 nums = [-1, 1, -6, 4, 5, -6, 1, 4, 1]：频次表是 {-1: 1, 1: 3, -6: 2, 4: 2, 5: 1}。频次为 1 的有 -1 和 5，按数值降序排成 5、-1；频次为 2 的有 -6 和 4，按数值降序排成 4、4、-6、-6；频次为 3 的只有 1，排成 1、1、1。拼起来是 [5, -1, 4, 4, -6, -6, 1, 1, 1]。最后看 nums = [1, 1, 2, 2, 2, 3]：频次表是 {1: 2, 2: 3, 3: 1}，结果是 [3, 1, 1, 2, 2, 2]——频次最小的 3 打头，其次是出现两次的 1，最后是出现三次的 2。

代码实现

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 排序规则：频次升序。
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)$。频次统计是一趟线性扫描，排序占主导；比较器内部只做常数次哈希查找与整数比较。
  • 空间复杂度：Java 为 $O(n)$，主要是装箱数组；Go 为 $O(k + \log n)$，其中 k 是不同值个数，来自频次表与排序栈。

关键点总结

  • 双关键字排序要在一个比较器里表达，先比主关键字、相等时再比次关键字。拆成两趟排序会依赖排序的稳定性，而多数语言对基本类型用的是不稳定排序。
  • 「频次升序 + 数值降序」落到比较器里，就是先比较 freq[a] 与 freq[b]，相等时反向比较 b 与 a。写完后用同频不同值的小用例核对方向。
  • 依赖全局统计量的比较器，其统计必须在排序开始前全部算完。比较器的调用顺序不可预测，边排边统计会读到不完整的数据。
  • Java 没有 Arrays.sort(int[], Comparator) 这个重载，要用自定义比较器就必须先装箱成 Integer[]。这是语言层面的硬约束，不是可选的风格。
  • Java 比较器优先使用 Integer.compare，避免换到更大值域后减法溢出并破坏全序性。
  • 面试视角：这题的考点是比较器的准确性，所以答题时应该口述规则再写代码——「主键是出现次数，升序；副键是数值本身，降序」，写完当场用一个频次相同的例子走一遍验证方向。面试官常追问「值域只有 201 种，能不能不排序」，标准答案是用桶：按频次分桶、桶内降序，做到 $O(n + k)$，能主动提出会显著加分。

易错点总结

  • 错误写法：频次相同时也返回 a - b，把两段方向写成同向。用例 nums = [2, 3, 1, 3, 2] → 结果是 [1, 2, 2, 3, 3]，正确答案是 [1, 3, 3, 2, 2]。
  • 错误写法：主关键字写成 fb - fa，把频次排成降序。用例 nums = [1, 1, 2, 2, 2, 3] → 结果是 [2, 2, 2, 1, 1, 3]，正确答案是 [3, 1, 1, 2, 2, 2]。
  • 脆弱写法：先按值降序，再依赖第二次排序的稳定性按频次升序。只有第二次排序明确稳定时才正确；换成不稳定实现会打乱同频段，一个比较器同时表达两级规则更可靠。
  • 错误写法：在比较器内部实时统计频次。用例 任意含重复元素的输入 → 比较器的调用次序不可预测，读到的频次是半成品，排序结果随实现而变。
  • 错误写法：Java 里直接对 int[] 调用 Arrays.sort(nums, comparator)。用例 任意输入 → 该重载不存在，编译失败；必须先装箱成 Integer[]。
  • 错误写法：排序后忘记把 Integer[] 写回 int[]，直接返回原始的 nums。用例 nums = [2, 3, 1, 3, 2] → 返回未改动的原数组，正确答案是 [1, 3, 3, 2, 2]。
  • 错误写法：统计频次时用 freq.put(v, freq.get(v) + 1) 而不做缺省处理。用例 任意输入 → 首次出现的值上 get 返回 null，拆箱抛空指针异常。
  • 错误写法：把「频次相同按数值降序」理解成「按原数组中首次出现的先后」。用例 nums = [2, 3, 1, 3, 2] → 得到 [1, 2, 2, 3, 3]，正确答案是 [1, 3, 3, 2, 2]。
  • 错误写法：Go 比较函数使用 <=。相同元素会同时满足 less(i,j) 与 less(j,i)，违反严格弱序，排序结果不再可靠；相等项必须返回 false。

相似题目

题目 难度 考察点
451. 根据字符出现频率排序 中等 频次降序且不要求次关键字，输出是重排后的字符串而非数组
347. 前 K 个高频元素 中等 只需频次最高的 K 个，可用堆或桶做到优于全排序的复杂度
692. 前K个高频单词 中等 双关键字同为「频次 + 字典序」，但两者方向的组合与本题相反
1122. 数组的相对排序 简单 主关键字由外部给定的顺序表决定，未出现的元素单独升序追加
1365. 有多少小于当前数字的数字 简单 同样利用有限值域做计数，再用前缀和一次性回答所有查询
179. 最大数 中等 比较器由字符串拼接结果定义，考察自定义全序的传递性证明
LCR 075. 数组的相对排序 简单 与 1122 同题，适合对比计数排序与比较器排序两种实现路径