[LeetCode] 451. Sort Characters By Frequency

題：https://leetcode.com/problems/sort-characters-by-frequency/description/

題目

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.

題目大意

按字元串 出現頻率高低 排列字元串。

思路

桶排序，一般按 頻率排序等，都可以考慮桶排序。

1. 統計 string，計算每個 char出現的頻率。
2. 桶排序，生成 bucketsList 數組 （長為 string的長度 + 1），List[i] 為出現了 第i次的字元的list。
3. 然後從高到低，周遊 bucketsList ，進行輸出。

class Solution {
    public String frequencySort(String s) {
        Map<Character,Integer>  frequencyMap = new HashMap<>();
        for(int i =0 ;i<s.length();i++)
            frequencyMap.put(s.charAt(i),frequencyMap.getOrDefault(s.charAt(i),0)+1);
        List<Character>[] bucketsList = new List[s.length()+1];
        
        for(char ch:frequencyMap.keySet()){
            if(bucketsList[frequencyMap.get(ch)]==null)
                bucketsList[frequencyMap.get(ch)] = new ArrayList<>();
            bucketsList[frequencyMap.get(ch)].add(ch);
        }
   
        StringBuilder res = new StringBuilder();
        for(int i = bucketsList.length-1;i>=1;i--)
            if(bucketsList[i]!=null)
                for(char ch:bucketsList[i])
                    for(int j = 0;j < i;j++)
                        res.append(ch);
        return res.toString();    
    }
}