[LeetCode] 451. Sort Characters By Frequency

轉自LeetCode

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"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.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"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.

<Solution>

參考解法

主要的想法是

• 先用一個 unordered_map 紀錄每個字元的頻率，key 是 char，value 是 frequency

    用 unordered_map 的原因是，不去打亂原本字母在字串裡出現的順序

• 再用一個 map ，key 是 frequency，value 是一個 vector<string> 來存字元

    用 vector<string> 來當value，是因為同一個頻率的字元，可能不只一個

    再用一個 map 並且拿 frequency 當 key 的原因是，map 會自動對 key 做升冪排序

    所以到時候逆向 iterate map，就可以從頻率最高的字元開始輸出

• 最後根據頻率，append 到最後的字串

c++

kotlin