力扣451：ASCII数组计数法 用128个桶解决频率排序问题

题目重解

给定一个字符串，将字符按照出现频率降序排列。例如输入"tree"，可能返回"eetr"或"eert"。题目要求我们不考虑字母顺序，只需保证相同字符相邻且高频字符在前。

解题思路

1.使用128大小的数组统计每个ASCII字符出现次数

2.每次遍历桶数组找出当前最大频率的字符

3.将该字符按出现次数追加到结果字符串

4.将该字符的计数清零避免重复处理

5.循环直到结果字符串长度等于原字符串

通过多次线性扫描实现了O(n)时间复杂度（严格来说是O(128n)），空间复杂度为O(128)。

代码详解

class Solution {
public:
    int bocket[128] = {0}; // ASCII码桶计数器
    
    string frequencySort(string s) {
        // 统计字符频率
        for (int i = 0; i < s.size(); i++) {
            bocket[s[i]]++; // 每个字符对应的ASCII码位置计数+1
        }
        
        string s1 = ""; // 结果字符串
        while (s1.size() < s.size()) {
            int maxidx = 0; // 当前最大频率字符的ASCII码
            
            // 找出当前频率最高的字符
            for (int i = 1; i < 128; i++) {
                if (bocket[i] > bocket[maxidx]) {
                    maxidx = i;
                }
            }
            
            // 将字符按频率追加到结果
            for (int i = 0; i < bocket[maxidx]; i++) {
                s1 += maxidx;
            }
            
            bocket[maxidx] = 0; // 已处理字符清零
        }
        return s1;
    }
};