451. 根据字符出现频率排序

Approach 1，map计数+优先队列排序

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Character> pq = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            pq.offer(entry.getKey());
        }

        StringBuilder res = new StringBuilder();
        while (!pq.isEmpty()) {
            Character c = pq.poll();
            int n = map.get(c);
            for (int i = 0; i < n; i++) {
                res.append(c);
            }
        }
        return res.toString();
    }
}

approach 2，数组计数+排序

与方法一是同一个做法，只是用数组替代了map（提高性能），list排序替代了优先队列，整体区别不大

class Solution {
    public String frequencySort(String s) {
        int[] map = new int[128];
        List<Integer> list = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (++map[(int)c] == 1) list.add((int)c);
        }
        Collections.sort(list, (a, b) -> map[(int)b] - map[(int)a]);
        
        StringBuilder ans = new StringBuilder();
        for (int c : list) {
            int cnt = map[c];
            for (int i = 0; i < cnt; i++) {
                ans.append((char)c);
            }
        }
        return ans.toString();
    }
}

approach 3，桶排序

class Solution {
    public String frequencySort(String s) {
        int[] map = new int[128];
        int maxCnt = 0;
        for (char c : s.toCharArray()) {
            if (++map[(int)c] > maxCnt) maxCnt = map[(int)c];
        }
        
        List<Character>[] bucket = new List[maxCnt + 1];
        for (int i = 0; i <= maxCnt; i++) bucket[i] = new ArrayList<>();
        for (int i = 0; i < 128; i++) {
            if (map[i] != 0) {
                bucket[map[i]].add((char)i);
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int i = maxCnt; i >= 0; i--) {
            if (bucket[i].size() != 0) {
                for (char c : bucket[i]) {
                    for (int j = 0; j < i; j++) ans.append(c);
                }
            }
        }
        return ans.toString();
    }
}