451. Sort Characters By Frequency

Leetcode 问题: 451. Sort Characters By Frequency
Categories:
Tags:

题目

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

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.

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.

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.

答案

JavaScript

  1. 先找出所有字母出现的频率有多少，产生 字母出现频率 Map
  2. 将字母出现频率 Map 反转，以频率当作 key，产生出，频率有哪些字母 Map
  3. 从较高频率往较低频率找，逐步将字串加到结果中
/**
 * @param {string} checkString
 * @return {string}
 */
var frequencySort = function(checkString) {
    // 字串频率对应 Map
    const letterFrequencyMap = new Map();
    // 最大字串出现频率
    let maxLetterFrequency = 1;
    for (let i in checkString) {
        let currentLetter = checkString[i];
        // 如果没有此对应字串，设定预设字串频率为 1
        let letterFrequency = 1;

        if (letterFrequencyMap.has(currentLetter)) {
            // 如果有此对应数字，将频率数字 ++
            letterFrequency = letterFrequencyMap.get(currentLetter) + 1;
        }

        if (maxLetterFrequency < letterFrequency) {
            // 如果有更高的出现频率，设定为目前最高频率
            maxLetterFrequency = letterFrequency;
        }
        // 设定字串频率
        letterFrequencyMap.set(currentLetter, letterFrequency);
    }



    // 取得对应频率，所有数字阵列资料
    const frequencyLetterBucketMap = new Map();
    letterFrequencyMap.forEach((letterFrequency, currentLetter) => {
        let letterFrequencyBucket = [];
        if (frequencyLetterBucketMap.has(letterFrequency)) {
            // 如果有此对应数字，将频率数字 ++
            letterFrequencyBucket = frequencyLetterBucketMap.get(letterFrequency);
        }
        // 将目前数字加入此频率阵列
        letterFrequencyBucket.push(currentLetter);
        // 设定频率阵列
        frequencyLetterBucketMap.set(letterFrequency, letterFrequencyBucket)
    });



    // 递增出现频率字串
    let decreasingFrequencyOrderString = '';
    // 取得 Top K 频率出现最高的数字
    for (let checkFrequency = maxLetterFrequency; checkFrequency >= 1; checkFrequency--) {
        if (!frequencyLetterBucketMap.has(checkFrequency)) {
            // 如果没有找到此频率字串，继续找下一个
            continue;
        }

        // 取得此频率数字清单
        let letterFrequencyBucket = frequencyLetterBucketMap.get(checkFrequency);

        for (let i in letterFrequencyBucket) {
            let currentLetter = letterFrequencyBucket[i];
            // 将此字串重複出现并加入到「递增出现频率字串」
            decreasingFrequencyOrderString += currentLetter.repeat(checkFrequency);
        }
    }

    return decreasingFrequencyOrderString;
};

参考资料