Pengjielee's blog

题目

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:
输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:
输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:
输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sort-characters-by-frequency 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、桶排序

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  const result = [];

  // 使用hashmap统计每个字符出现的次数
  const hashmap = new Map();
  for (let ch of s) {
    if (!hashmap.has(ch)) {
      hashmap.set(ch, 0);
    }
    hashmap.set(ch, hashmap.get(ch) + 1);
  }

  // 创建桶，桶的个数为 s 的长度 +1，因为 buckets[0] 没有意义
  const buckets = new Array(s.length + 1);
  // 按字符出现的次数i ，放入第i个桶里
  for (let [key, value] of hashmap) {
    if (!buckets[value]) {
      buckets[value] = [];
    }
    buckets[value].push(key);
  }

  // 遍历每一个桶（倒序遍历）
  for (let i = buckets.length - 1; i > 0; i--) {
    // 如果桶中有字符
    if (buckets[i]) {
      //遍历桶中的字符
      for (let ch of buckets[i]) {
        //字符出现几次就向result中添加几次字符
        for (let j = i; j > 0; j--) {
          result.push(ch);
        }
      }
    }
  }

  return result.join("");
};