跳至主要內容

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


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

🟠   🔖  哈希表 字符串 桶排序 计数 排序 堆(优先队列)  🔗 力扣open in new window LeetCodeopen in new window

题目

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+🟠🀄️open in new window 🔗open in new window
387字符串中的第一个唯一字符队列 哈希表 字符串 1+🟢🀄️open in new window 🔗open in new window
1636按照频率将数组升序排序数组 哈希表 排序🟢🀄️open in new window 🔗open in new window
2278字母在字符串中的百分比字符串🟢🀄️open in new window 🔗open in new window
2341数组能形成多少数对数组 哈希表 计数🟢🀄️open in new window 🔗open in new window
2374边积分最高的节点 哈希表🟠🀄️open in new window 🔗open in new window
2404出现最频繁的偶数元素数组 哈希表 计数🟢🀄️open in new window 🔗open in new window
2506统计相似字符串对的数目位运算 数组 哈希表 2+🟢🀄️open in new window 🔗open in new window