Sort Characters By Frequency

题目：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.
      

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.      

解析：可以使用排序把字符进行一遍快排，当然时间复杂度时O(nlogn)

           这里使用二次hash结构，第一次统计每种字符出现的次数，第二次以出现的次数作为下标，来表示出现次数与对应字符串，以出现次数从大到小输出字符串即可

代码：

class Solution {
public:
    string frequencySort(string s) {
        int table[266];
        for (int i=0; i<266; i++)
        {
            table[i]=0;
        }
        for (int i=0; i<s.size(); i++)
        {
           table[s[i]]++;
        }
        vector<string>ttable(s.size()+1,"");
        for (int i=0; i<256; i++)
        {
            ttable[table[i]].append(table[i],char(i));
        }
        string ans="";
        for (int i=s.size(); i>=0; i--)
        {
            ans.append(ttable[i]);
        }
        return ans;
    }
};