451. 根据字符出现频率排序

🟠   🔖  哈希表 字符串 桶排序 计数 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

Input: s = "tree"

Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once.

So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"

Output: "aaaccc"

Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.

Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"

Output: "bbAa"

Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.

Note that 'A' and 'a' are treated as two different characters.

Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of uppercase and lowercase English letters and digits.

题目大意

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

解题思路

可以使用哈希映射来实现：

1. 使用哈希映射存储字符串中每个元素的频率。
2. 依据字符出现的频次对字符进行排序。
3. 遍按照题目要求的格式返回结果。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是字符串的长度。
  • 这个算法的时间复杂度主要由排序操作决定，因此它的时间复杂度是 O(n log n)，其中 n 是字符串的长度。
  • 在排序步骤中，我们对字符集进行排序，而字符集的大小是常数级别的（26 个英文字母和一些数字），因此排序的复杂度可以看作是 O(1)。
• 空间复杂度：O(k)，k 为哈希表中最大存储的字符数。

代码

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
	// 使用哈希表统计字符频率
	let map = new Map();
	for (let i of s) {
		map.set(i, map.has(i) ? map.get(i) + 1 : 1);
	}

	// 根据频率对字符进行排序
	const arr = Array.from(map.keys()).sort((a, b) => map.get(b) - map.get(a));

	// 构建结果字符串
	let res = '';
	for (const char of arr) {
		res += char.repeat(map.get(char));
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
347	前 K 个高频元素	[✓]	数组 哈希表 分治 5+	🟠	🀄️ 🔗
387	字符串中的第一个唯一字符	[✓]	队列 哈希表 字符串 1+	🟢	🀄️ 🔗
1636	按照频率将数组升序排序	[✓]	数组 哈希表 排序	🟢	🀄️ 🔗
2278	字母在字符串中的百分比		字符串	🟢	🀄️ 🔗
2341	数组能形成多少数对		数组 哈希表 计数	🟢	🀄️ 🔗
2374	边积分最高的节点		图 哈希表	🟠	🀄️ 🔗
2404	出现最频繁的偶数元素		数组 哈希表 计数	🟢	🀄️ 🔗
2506	统计相似字符串对的数目		位运算 数组 哈希表 2+	🟢	🀄️ 🔗