Code & Func

第7天了

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

Example 1:

1
Input:
2
"tree"
3

4
Output:
5
"eert"
6

7
Explanation:
8
'e' appears twice while 'r' and 't' both appear once.
9
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

1
Input:
2
"cccaaa"
3

4
Output:
5
"cccaaa"
6

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

Example 3:

1
Input:
2
"Aabb"
3

4
Output:
5
"bbAa"
6

7
Explanation:
8
"bbaA" is also a valid answer, but "Aabb" is incorrect.
9
Note that 'A' and 'a' are treated as two different characters.

比较简单的一道题，具体解法如下：

计数算频率，用unordered_map就搞定了
按频率排序，先把unoredred_map转成vector，然后再sort
生成字符串。

具体代码如下：

1
string frequencySort(string s) {
2
    unordered_map<char, int> cmap;
3
    for(int i = 0;i < s.size(); i++) cmap[s[i]]++;
4
    vector<pair<char, int>> pvec(cmap.begin(), cmap.end());
5
    sort(pvec.begin(), pvec.end(), [](const pair<char, int> &p1, const pair<char, int> &p2) {
6
        return p1.second > p2.second;
7
    });
8

9
    string res;
10
    for(auto it = pvec.begin(); it != pvec.end(); ++it) {
11
        res += string(it->second, it->first);
12
    }
13
    return res;
14
}

因为中途需要把unordered_map转成vector，所以使用的空间就有点多了（统计数据存了两份），所以我们尝试直接使用vector来统计。之所以能直接用vector来统计，是因为char类型总共就256个字符而已，所以我们用一个长度为256的vector即可完成，具体代码如下：

1
string frequencySort(string s) {
2
    vector<pair<char, int> > pvec(256);
3
    for(int i = 0;i < 256; i++) pvec[i] = make_pair(i, 0);
4
    for(int i = 0;i < s.size(); i++) {
5
        pvec[s[i]].second++;
6
    }
7

8
    string res;
9
    for(auto it = pvec.begin(); it != pvec.end() && it->second; ++it) {
10
        res += string(it->second, it->first);
11
    }
12
    return res;
13
}