451. 根据字符出现频率排序【C++】

超、凢脫俗 2022-10-12 04:18 115阅读 0赞

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:  
"tree"

输出:  
"eert"

解释:  
'e'出现两次，'r'和't'都只出现一次。  
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。  
示例 2:

输入:  
"cccaaa"

输出:  
"cccaaa"

解释:  
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。  
注意"cacaca"是不正确的，因为相同的字母必须放在一起。  
示例 3:

输入:  
"Aabb"

输出:  
"bbAa"

解释:  
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。  
注意'A'和'a'被认为是两种不同的字符。

class Solution {
    public:
        string frequencySort(string s) {
            int a['z'+1]={0};
            char r[s.size()+1];
            for(int i = 0;i<s.size();i++)
            {
                a[s[i]]++;
            }
            vector<int> t;
            for(int i = 0;i<='z';i++)
            {
                if(a[i]>0)
                {
                    t.push_back(a[i]);
                }
            }
            sort(t.begin(),t.end());
            string ret;
            int cnt=0;
            for(int i =t.size()-1;i>=0;i--)
            {
                //cout<<"i: "<<t[i]<<endl;
                for(int j = 0;j<='z';j++)
                {
                    if(a[j]==t[i])
                    {
                        while(a[j]>0)
                        {
                            r[cnt++]=char(j);
                            // ret=char(j)+ret;//直接重组太费时间了
                            a[j]--;
                        }
                    }
                }
            }
            r[cnt]=0;
            return string(r);
        }
    };