[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>

參考解法

Thoughts as following:

  • Use an unordered_map to store the frequency of each char. The key is the character and the value is the frequency.
  • Use one more map. The key is the frequency and the value is a vector<string> to store characters。The reason to use vector<string> to store characters is there might be more than one character have the same frequency. And the reason to use one more map is map will sort the data in increasing order based on key. Therefore, the highest frequent character will be the last element of map.
  • Append all the characters to the string according their frequency.
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.