451. Sort Characters By Frequency

Posted on | In , |

题目

https://leetcode.com/problems/sort-characters-by-frequency/description/

-w951
-w946

想法

按照频率排序

如果用一个map来存放，sort一下就可以了
空间利用率有点高？
先写一个再说吧

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string frequencySort(string s) {
        map<char, int> m;
        for (char ch : s) {
            m[ch]++;
        }
        vector<pair<char, int>> v;
        for (auto t : m) {
            v.push_back(t);
        }
        sort(v.begin(), v.end(), [](pair<char, int>& a, pair<char, int>& b){
           return a.second > b.second;
        });
        string res;
        for (auto& t : v) {
            res += string(t.second, t.first);
        }
        return res;
    }
};

虽然空间复杂度有点高，但是也AC了。

这里注意，自己本来想sort一个map，试了之后才知道cpp的map不能被sort，最便利的排序方式是转存到vector~