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

🟢   🔖  数组 哈希表 排序  🔗 力扣 LeetCode

题目

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

解题思路

1. 统计频率：

   • 使用哈希表 freq 存储每个数字的频率。键是数字，值是该数字出现的次数。

2. 排序频率表：

   • 将 freq 转化为数组，按以下规则排序：
     • 优先按频率升序排列。
     • 如果频率相同，则按数字降序排列。

3. 生成结果数组：

   • 根据排序后的频率表，依次将数字填入结果数组，每个数字出现的次数等于其频率。

复杂度分析

• 时间复杂度：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+	🟢	🀄️ 🔗