451.根据字符出现频率排序

/**
 * @param {string} s
 * @return {string}
 */
// 按照字符出现频率排序
var frequencySort = function (s) {
    let map = new Map() // 统计字符出现频率
    for (let i = 0; i < s.length; i++) {
        let char = s.charAt(i)
        if (map.has(char)) {
            map.set(char, map.get(char) + 1)
        } else {
            map.set(char, 1)
        }
    }
    console.log(map)

    // map转为数组，每一项是[key, value]
    const arr = Array.from(map)
    // 按照出现频率排序
    arr.sort((a, b) => b[1] - a[1])

    // 再重新构造字符串
    let res = ''
    for (let i = 0; i < arr.length; i++) {
        let [char, count] = arr[i]
        for (let j = 0; j < count; j++) {
            res += char
        }
    }

    return res
};

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
    // 借鉴桶排序思想
    // 1.统计每个字符出现频率，并记录最高频率maxFreq
    // 2.创建1到maxFreq的桶，存储相应频率的字符
    // 3.按频率从大到小遍历桶，获取频率对应字符串，进行拼接

    let map = new Map()
    let maxFreq = 0
    // 统计每个字符出现频率，并记录最大频率
    for (let i = 0; i < s.length; i++) {
        let char = s.charAt(i)
        let freq = map.get(char) || 0
        freq = freq + 1

        map.set(char, freq) // 统计频率
        maxFreq = Math.max(maxFreq, freq) // 记录最大值
    }

    // 创建1到maxFreq的桶，桶编号从1开始
    const buckets = new Array(maxFreq + 1).fill(0).map(() => [])
    // 把元素放到对于频率的桶
    for (let [char, freq] of map) {
        buckets[freq].push(char)
    }
    console.log(buckets)

    let res = []
    // 频率从大到小遍历桶，构造字符串
    for (let freq = maxFreq; freq >= 1; freq--) {
        let chars = buckets[freq] // freq频率对应的字符列表
        for (let i = 0; i < chars.length; i++) {
            let char = chars[i]
            // 每个字符出现freq次
            for (let j = 0; j < freq; j++) {
                res += char
            }
        }
    }

    return res
}

console.log(frequencySort('tree'))