451. Sort Characters By Frequency(桶排序)

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.

class Solution {

public:

    //桶排序。将相同长度的子串放到同一个桶中，最后利用桶排序

    string frequencySort(string s) {
　　　　 //防止s="aaa"  插入 b[3] = "aaa";

        vector<string> bucket(s.size()+1,"");

        map<char,int> m;

        string res;

        for(int i=0;i<s.size();i++){

            m[s[i]]++;

        }

        for(auto sub:m){

            int n = sub.second;

            int c = sub.first;

            //长度为n的子串都放到bucket[n]

            bucket[n].append(string(n,c));

        }

        //最后利用桶排序，倒序遍历桶即可

        for(int i=bucket.size()-1;i>=0;i--){

            res.append(bucket[i]);

        }

        return res;

    }

};

巴特西

451. Sort Characters By Frequency(桶排序)

最新文章

热门文章