LeetCode-Go 题解 | 1636. Sort Array by Increasing Frequency频次升序、同频降序的双键排序实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章围绕 LeetCode 第 1636 题「Sort Array by Increasing Frequency按频率递增排序数组」展开以 LeetCode-Go 仓库中该题的 README 文档为主体结合 源码实现 与 测试用例 进行纵深剖析。读完本文你将掌握哈希统计频率 自定义比较器这一双键排序的通用套路并能直接复现、验证该题的 Go 解法。题目描述给定一个整数数组nums请你将数组按照每个值的频率frequency升序排序。如果有多个值的频率相同则按照数值本身降序排序。最后返回排序后的数组。示例 1输入nums [1,1,2,2,2,3] 输出[3,1,1,2,2,2] 解释3 出现 1 次1 出现 2 次2 出现 3 次按频率升序排列。示例 2输入nums [2,3,1,3,2] 输出[1,3,3,2,2] 解释2 和 3 都出现 2 次频率相同因此按数值降序排列3 在 2 之前。示例 3输入nums [-1,1,-6,4,5,-6,1,4,1] 输出[5,-1,4,4,-6,-6,1,1,1]约束条件1 nums.length 100-100 nums[i] 100题目大意对数组中的元素按其出现频次从小到大排序当两个元素的出现频次相等时数值较大的元素排在前。核心规则可以概括为一句话频率升序为第一关键字数值降序为第二关键字。解题思路这是一道简单题解题链路非常清晰分为两步统计频率遍历数组用哈希表map记录每个数值出现的次数自定义排序对数组调用sort.Slice传入自定义比较器——先比较两个元素的频率频率小者在前若频率相等再比较数值本身数值大者在前。由于排序规则构成了对(频率, 数值)二元组的全序关系任意两个元素都能唯一比较出先后因此无需关心sort.Slice是否稳定结果都是确定且正确的。Go 源码实现与逐行剖析仓库中 1636. Sort Array by Increasing Frequency.go 的完整实现如下package leetcode import sort func frequencySort(nums []int) []int { freq : map[int]int{} for _, v : range nums { freq[v] } sort.Slice(nums, func(i, j int) bool { if freq[nums[i]] freq[nums[j]] { return nums[j] nums[i] } return freq[nums[i]] freq[nums[j]] }) return nums }逐段解读频率统计阶段freq : map[int]int{}建立数值 → 出现次数的映射。for _, v : range nums { freq[v] }一趟线性扫描即可完成统计时间复杂度 O(n)。由于题目约束-100 nums[i] 100map 的键始终落在有限小范围内哈希冲突可控性能表现稳定。排序阶段sort.Slice(nums, func(i, j int) bool {...})对原数组原地排序。比较器的两个分支正是题目规则的直接翻译当freq[nums[i]] freq[nums[j]]时频率相同返回nums[j] nums[i]即数值大的元素排在前面降序否则返回freq[nums[i]] freq[nums[j]]即频率小的元素排在前面升序。返回阶段直接返回nums因为sort.Slice是原地排序无需额外分配新数组空间开销仅为频率表本身。值得注意的边界情况负整数示例 3 中包含-1、-6等负数比较器按数值降序时nums[j] nums[i]对负数的比较同样成立无需特殊处理全部元素频率相同此时比较器退化为纯数值降序如输入[2,3,1,3,2]中2、3频率都为 23排在2前面与示例 2 输出[1,3,3,2,2]一致单元素数组sort.Slice对长度小于等于 1 的切片不做任何交换直接返回天然安全。稳定性讨论为什么不需要sort.SliceStableGo 标准库的sort.Slice使用的是不稳定排序快速排序的变体而sort.SliceStable则保证相等元素的相对顺序不变。本题中两个元素只要可比较比较器就一定能给出严格先后顺序——频率不等按频率排频率相等按数值排不存在比较器判定相等的情况。因此排序结果是全序唯一确定的sort.Slice的稳定性特性在这里不影响正确性这也是该实现可以放心使用sort.Slice的原因。复杂度分析时间复杂度O(n log n)。其中 O(n) 用于一趟扫描统计频率O(n log n) 为sort.Slice的排序开销n为nums的长度。空间复杂度O(n)。主要由频率哈希表freq承担最坏情况下每个数值都不同map 中最多存储 n 个键值对排序本身为原地操作不产生额外数组。测试验证仓库用例与覆盖率机制仓库为本题提供了与 README 中三个示例一一对应的单元测试位于 1636. Sort Array by Increasing Frequency_test.goqs : []question1636{ {para1636{[]int{1, 1, 2, 2, 2, 3}}, ans1636{[]int{3, 1, 1, 2, 2, 2}}}, {para1636{[]int{2, 3, 1, 3, 2}}, ans1636{[]int{1, 3, 3, 2, 2}}}, {para1636{[]int{-1, 1, -6, 4, 5, -6, 1, 4, 1}}, ans1636{[]int{5, -1, 4, 4, -6, -6, 1, 1, 1}}}, }测试用例覆盖了三种典型场景频率全部不同的数组、存在同频元素的数组、以及包含负数和多种频率组合的数组。函数Test_Problem1636遍历全部用例将输入输出打印到终端并断言结果正确。你可以在仓库根目录下运行以下命令验证本题实现# 运行单个题目的测试目录名含空格需用引号包裹 go test -v -run Test_Problem1636 ./leetcode/1636.Sort-Array-by-Increasing-Frequency/ # 或运行整个 leetcode 包下的全部测试 go test ./leetcode/...仓库根目录还提供了 gotest.sh 脚本其中执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...即对leetcode包下全部题目统一进行带覆盖率采集的测试生成 coverage.txt 覆盖率文件这也是仓库实现 100% 测试覆盖率的保障机制。测试代码中通过fmt.Printf(【input】:%v 【output】:%v, p, frequencySort(p.nums))的方式输出运行结果方便对照。延伸思考基于约束条件的其他实现路径除了上述哈希表 自定义比较器的通用做法结合本题约束-100 nums[i] 100还可以推演出以下优化思路供读者自行验证这些属于本文的推导分析并非仓库现有代码定长数组替代 map 统计频率由于数值范围固定为 201 个整数可以使用长度 201 的数组索引偏移 100替代哈希表统计频率将频率统计的哈希开销降为数组随机访问常数更小。频次桶分组重建数组先统计频率再按出现次数分桶每个桶内按数值降序排列最后按桶的频次从小到大拼接输出。该思路的时间复杂度仍为 O(n log n)桶内排序但思路更贴近频率分层的语义适合在面试中作为第二解法展示。两种思路的核心都未脱离统计频率 → 双键排序的框架读者可以在掌握仓库实现后自行编写对照版本并用 测试文件 中的用例进行回归验证。小结LeetCode 1636 题是哈希统计 自定义比较器这一类排序问题的标准模板先用一趟线性扫描建立频率表再通过sort.Slice的自定义比较器把频率升序、同频值降序的双键规则直接翻译成 Go 代码。整个实现只有十余行却完整覆盖了题目全部语义且对负整数、同频元素、单元素等边界情况都天然安全。结合仓库中配套的测试用例与覆盖率机制读者可以快速验证并内化这一套路将其迁移到其他按属性排序类问题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考