跳至主要內容

451. Sort Characters By Frequency

451. Sort Characters By Frequencyopen 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 是字符串的长度。在排序步骤中，我们对字符集进行排序，而字符集的大小是常数级别的（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)
Copyright © 2024 2xiao