451 根据字符出现频率排序

题目

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

示例 1:

输入:
"tree"

输出:
"eert"

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

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

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

示例 3:

输入:
"Aabb"

输出:
"bbAa"

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

题解

1. 既然要按照字符出现的顺序降序排列，那么就需要知道每个字符出现的次数，所以首先进行一次遍历，并设置字符为 key，依次递增出现的次数；重要的思路就是使用一个二维数组来储存，其中出现的次数为下标，第二维数组为出现的字符；再一次遍历这个二维数组，并依次拼接这个二维数组即可。

TIP

执行用时：96 ms, 在所有 JavaScript 提交中击败了 89.95% 的用户
内存消耗：40.9 MB, 在所有 JavaScript 提交中击败了 55.74% 的用户

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    let map = new Map()  // 统计字符和出现的次数
    let resultList = []  // 二维数组
    let result = ''  // 最后的字符

    for(let i=0;i<s.length;i++) {
        let item = s.charAt(i) // 获取当前字符
        let val = map.get(item)  // 获取 map 里面的值
        // 每次都进行重置：如果存在，则 +1，否则设置为 1
        map.set(item, val == undefined ? 1 : val+1)
    }
    
    // 使用 for of 来遍历 Map 结构
    // 设置 二维数组的值
    for(let [key, val] of map) {
        // 如果对应数组里值为空的话，则设置为 []
        if(resultList[val] == undefined) {
            resultList[val] = [key]
        } else {
            // push 值
            resultList[val].push(key)
        }
    }

    for(let i=resultList.length-1;i>0;i--) {
        let item = resultList[i] // 当前二维数组的值
        // 如果为数组
        if(Array.isArray(item)) {
            let {length: l} = item
            // 一个遍历二维数组的 while循环
            while(l--) {
                // 使用 repeat 拼接好该出现的次数
                let str = item[l].repeat(i)
                result += str
            }
        }
    }
    
    return result
};

• 时间复杂度： `O(n^2)`，分别使用三个 for循环，其中第三个 for循环内使用了 while循环（假设 repeat 方法为 O(1)）。
• 空间复杂度： `O(n)`，使用三个变量数组对象来储存值
• 最好情况：
• 最坏情况：