【Leetcode】451. 根据出现的频率对字符排序（Sort Characters By Frequency）

Leetcode - 451 Sort Characters By Frequency (Medium)

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.

解题思路：桶排序，使用元素的出现频次作为下标。

public String frequencySort(String s) {
    List<Character>[] bucket = new List[s.length() + 1];
    Map<Character, Integer> frequencyMap = new HashMap<>();
    
    for (char c : s.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }
    
    for (char key : frequencyMap.keySet()) {
        int frequency = frequencyMap.get(key);
        if (bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(key);
    }
    
    StringBuffer sb = new StringBuffer();
    for (int i = bucket.length - 1; i > 0; i--) {
        if (bucket[i] == null) continue;
        for (char c : bucket[i]) {
            for (int j = i; j > 0; j--) {
                sb.append(c);
            }
        }
    }
    
    return sb.toString();
}