1636. 按照频率将数组升序排序
1636. 按照频率将数组升序排序
题目
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
,请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同,请你按照数值本身将它们 降序 排序。
请你返回排序后的数组。
示例 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:
输入: 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
解题思路
统计频率:
- 使用哈希表
freq
存储每个数字的频率。键是数字,值是该数字出现的次数。
- 使用哈希表
排序频率表:
- 将
freq
转化为数组,按以下规则排序:- 优先按频率升序排列。
- 如果频率相同,则按数字降序排列。
- 将
生成结果数组:
- 根据排序后的频率表,依次将数字填入结果数组,每个数字出现的次数等于其频率。
复杂度分析
时间复杂度:
O(n + m log m)
- 统计频率:
O(n)
,n
是数组长度。 - 排序:
O(m log m)
,m
是数字种类数(freq
中的键数目)。 - 构造结果数组:
O(n)
。 - 总体时间复杂度为
O(n + m log m)
。
- 统计频率:
空间复杂度:
O(m)
,其中m
是数字种类数,使用了freq
存储频率。
代码
/**
* @param {number[]} nums
* @return {number[]}
*/
var frequencySort = function (nums) {
let freq = new Map();
// 统计频率
for (let num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
// 排序频率表
const sortedFreq = Array.from(freq).sort((a, b) => {
if (a[1] === b[1]) return b[0] - a[0]; // 频率相同时按数字降序
return a[1] - b[1]; // 频率升序
});
// 构造结果数组
let i = 0;
for (let [key, val] of sortedFreq) {
while (val--) {
nums[i++] = key;
}
}
return nums;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
451 | 根据字符出现频率排序 | [✓] | 哈希表 字符串 桶排序 3+ | 🟠 | 🀄️ 🔗 |
2190 | 数组中紧跟 key 之后出现最频繁的数字 | [✓] | 数组 哈希表 计数 | 🟢 | 🀄️ 🔗 |
2206 | 将数组划分成相等数对 | [✓] | 位运算 数组 哈希表 1+ | 🟢 | 🀄️ 🔗 |
2341 | 数组能形成多少数对 | [✓] | 数组 哈希表 计数 | 🟢 | 🀄️ 🔗 |
2374 | 边积分最高的节点 | 图 哈希表 | 🟠 | 🀄️ 🔗 | |
2418 | 按身高排序 | 数组 哈希表 字符串 1+ | 🟢 | 🀄️ 🔗 |