451. Sort Characters By Frequency

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Solution

哈希表记录字符出现的频率。然后将其添加到优先队列中。
最后根据优先级队列的顺序，加入每个字符对应的哈希表中记录的字符数。
理论上也可以用数组记录频率，但是问题中字符较复杂故未采用。

Code

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        PriorityQueue<Character> pq = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));
        StringBuffer sb = new StringBuffer();
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        for(char c : map.keySet()){
            pq.add(c);
        }
        while(!pq.isEmpty()){
            char c = pq.poll();
            for(int i = 0; i < map.get(c); i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}