【LeetCode】 451. Sort Characters By Frequency

Description

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

給予一個字串，根據每個字母出現的頻率進行遞減排序。

Example:

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

• 先使用map得到每個字母出現的次數，然後我們要根據value排序並重新輸出。
• 問題來了，我們要怎麼根據value排序map呢？其實因為map的結構所以無法直接做到，我們這邊的做法是結合vector和pair得到一個可排序的map。
• 先利用pair<char, int>得到字元和次數的映射關係，再依序用迴圈把每個組合都放到vector裡面。
• 最後將vector排序就好了，記得定義比較的function。

Code

typedef pair<char, int> Pair;
bool my_compare(const Pair &p1, const Pair &p2){
	return p1.second > p2.second;
}

class Solution {
public:
    string frequencySort(string s) {
        string str;
        map<char, int> m;
        vector<Pair> v;
        for(auto c : s)
            m[c]++;
        
        for(auto itr = m.begin(); itr != m.end(); ++itr)
        {
            v.push_back(make_pair(itr->first, itr->second));
        }

        sort(v.begin(), v.end(), my_compare);
        
        for(auto e : v)
            for(int i = 0; i < e.second; i++)
                str += e.first;
        return str;
    }
};

tags: LeetCode C++