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;
};

參考資料