一、题目

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

点击查看原题
难度级别： 中等

二、思路

1）hashMap+优先队列

使用哈希表记录每个字符出现过多少次
使用优先队列将字符从高频到低频排列，并将其组织成字符串

三、代码

1）hashMap+优先队列

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<Node> pq = new PriorityQueue<Node>((n1, n2)->{
            return n2.cnt -n1.cnt;
        });
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            pq.offer(new Node(entry.getKey(), entry.getValue()));
        }
        StringBuilder builder = new StringBuilder();
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int cnt = node.cnt;
            while (cnt-- > 0) {
                builder.append(node.c);
            }
        }
        return builder.toString();
    }
    public class Node {
        public char c;
        public int cnt;
        public Node(char c, int cnt) {
            this.c = c;
            this.cnt = cnt;
        }
    }
}

时间复杂度为O(n*logn)，空间复杂度为O(n)