# 451. 根据字符出现频率排序 [Medium][HashMap][Bucket]

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

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

示例 3:

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

題解思路：

1. 先遍歷字串，使用hashmap對每個字元頻率進行統計
2. 遍歷統計好hashmap中，以鍵值對{字元, 詞頻}形式放入priorityqueue中，並規定排序邏輯為：
1. 如果詞頻不等時，依照詞頻降冪排序
2. 如果詞頻相等時，依照字元字典序升冪排序。
3. 從priorityqueue中依序彈出，構建答案。

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int n = s.length();
        for(int i=0;i<n;i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c,0)+1);
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            return a[1] != b[1] ? b[1] -a[1]: a[0] - b[0];
            //如果字頻不相等時，依照字頻降冪排序，如果字頻相等時，依照字元順序升冪排序。
        });
        for(char c: map.keySet()){
            q.add(new int[]{c, map.get(c)});
        }

        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty()){
            int[] poll = q.poll();
            int c = poll[0], k = poll[1];
            while(k >0){
                sb.append((char)c);
                k--;
            }

        }
        return sb.toString();

    }
}