Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
1 2 3 4 5 6 7 8 9 |
<b>Input:</b> "tree" <b>Output:</b> "eert" <b>Explanation:</b> '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:
1 2 3 4 5 6 7 8 9 |
<b>Input:</b> "cccaaa" <b>Output:</b> "cccaaa" <b>Explanation:</b> 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:
1 2 3 4 5 6 7 8 9 |
<b>Input:</b> "Aabb" <b>Output:</b> "bbAa" <b>Explanation:</b> "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters. |
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: string frequencySort(string s) { map<char, int> f; for(char c:s) ++f[c]; vector<pair<int,char>> v; for(auto& kv : f) v.push_back({kv.second, kv.first}); sort(v.rbegin(), v.rend()); stringstream ans; for(auto& kv : v) ans << string(kv.first, kv.second); return ans.str(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment