451. Sort Characters By Frequency
451. Sort Characters By Frequency
🟠 🔖 哈希表
字符串
桶排序
计数
排序
堆(优先队列)
🔗 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
是字符串的长度。在排序步骤中,我们对字符集进行排序,而字符集的大小是常数级别的(26 个英文字母和一些数字),因此排序的复杂度可以看作是 O(1)
。
代码
/**
* @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 个高频元素](./0347.md)
- [387. 字符串中的第一个唯一字符](https://leetcode.com/problems/first-unique-character-in-a-string)
- [1636. 按照频率将数组升序排序](https://leetcode.com/problems/sort-array-by-increasing-frequency)
- [2278. 字母在字符串中的百分比](https://leetcode.com/problems/percentage-of-letter-in-string)
- [2341. 数组能形成多少数对](https://leetcode.com/problems/maximum-number-of-pairs-in-array)
- [2374. 边积分最高的节点](https://leetcode.com/problems/node-with-highest-edge-score)
- [2404. 出现最频繁的偶数元素](https://leetcode.com/problems/most-frequent-even-element)
- [2506. 统计相似字符串对的数目](https://leetcode.com/problems/count-pairs-of-similar-strings)