451. 根据字符出现频率排序
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
,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案,返回其中任何一个。
解题思路
可以使用哈希映射来实现:
- 使用哈希映射存储字符串中每个元素的频率。
- 依据字符出现的频次对字符进行排序。
- 遍按照题目要求的格式返回结果。
复杂度分析
- 时间复杂度:
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+ |