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

题目

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

示例

输入:
“tree”
输出:
“eert”

输入:
“cccaaa”
输出:
“cccaaa”

输入:
“Aabb”
输出:
“bbAa”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-characters-by-frequency
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1

Python实现

class Solution:
    def frequencySort(self, s: str) -> str:
        c=collections.Counter(s)
        cc=sorted(c.items(),key=lambda x:x[1],reverse=True)
        res=list()
        for i,v in cc:
            for j in range(v):
                res.append(i)
        return "".join(res)

Java实现

class Solution {
    public String frequencySort(String s) {
        // 存储每个字符的次数
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
        }
        List<Character> list = new ArrayList<>(hashMap.keySet());
        // 降序排序
        Collections.sort(list, (a, b) -> hashMap.get(b) - hashMap.get(a));
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < list.size(); i++) {
            char ch = list.get(i);
            int freq = hashMap.get(ch);
            for (int j = 0; j < freq; j++) {
                res.append(ch);
            }
        }

        return res.toString();
    }
}

方法2：优先队列

Java实现

class Solution {
    public String frequencySort(String s) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Character> pq = new PriorityQueue<>((o1, o2) -> map.get(o2) - map.get(o1));
        pq.addAll(map.keySet());

        StringBuffer sb = new StringBuffer();

        while(!pq.isEmpty()) {
            char c = pq.poll();
            for (int i = 0; i < map.get(c); i++) sb.append(c);
        }
        return sb.toString();
    }
}