# LeetCode 451. Sort Characters

@(LeetCode)

问题描述

给定一个字符串，将其按照每个字符出现的频次从高到低排序。

栗1：

输入："tree"
输出："eert"

解释：e 出现的频次为 2，r 和 t 分别为 1。eetr 也是正确答案。

栗2：

输入："cccaaa"
输出："cccaaa"

解释：
c 和 a 出现的频次都为 3，所以 cccaaa 和 aaaccc 都是正确答案。

栗3：

输入："Aabb"
输出："bbAa"

解释：
b 出现 2 次，A 和 a 分别出现一次。所以 bbAa 和 bbaA 都是正确答案。

想看英文原文的戳这里。

解题思路

这道题目比较简单。

主要涉及两个要点：

1. 求字符出现的频次

   使用 map 可以计算得出。

2. 频次排序

   有两种处理方式。

   • 直接将 map 根据 value 进行排序，然后遍历 map，按照每个字符的频次组成字符串。

   • 另一种方式，不排序，使用数组处理。将频次作为下标，频次对应的不同字符作为数组的值，最后反向遍历数组即可。

关键代码

1. 求字符频次：

   let map = new Map()
   let i = 0
   while (i < s.length) {
       if (map.has(s[i])) {
           const count = map.get(s[i])
           map.set(s[i], count + 1)
       } else {
           map.set(s[i], 1)
       }
   
       i += 1
   }
   

2. map 根据 value 排序

   // map 根据 value 从大到小排序
   const sortedMap = new Map([...map].sort((a, b) => {
       return b[1] - a[1]
   }))
   
   let str = ''
   sortedMap.forEach((value, key) => {
       let j = 0
       // 拼字符串
       while (j < value) {
           str += key
           j += 1
       }
   })
   

3. 使用数组，不排序

   // 初始化数组
   let frequencyList = new Array()
   let j = 0
   while (j < maxCount + 1) {
       frequencyList.push("")
       j += 1
   }
   
   // 以频次作为下标
   map.forEach((value, key) => {
       let totalString = frequencyList[value]
   
       // 拼字符串
       let k = 0
       let str = ""
       while (k < value) {
           str += key
           k += 1
       }
   
       totalString += str
       frequencyList[value] = totalString
   })
   
   // 倒序遍历，即频次最高的在前
   let result = ""
   let k = frequencyList.length - 1
   while (k >= 0) {
       result += frequencyList[k]
       k -= 1
   }
   

点此查看具体代码。