跳至主要內容

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


451. 根据字符出现频率排序open in new window

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