LEETCODE 451. Sort Characters By Frequency 解题思路分析

题目大意：

根据字符出现频率排序

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

示例 1:

输入:
"tree"

输出:
"eert"

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

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

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

示例 3:

输入:
"Aabb"

输出:
"bbAa"

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=451

解题思路分析：

1. 首先使用一个HashMap统计出每种字符出现的次数。map中key为字符，value为该字符出现次数。
2. 接下来使用PriorityQueue为出现次数排序，PriorityQueue的泛型是一个对象，每个对象中记录一种字符，以及该字符出现的次数（实际上就是将第一步生成的HashMap转存入Queue中），然后按顺序输出PriorityQueue中的每个字符并打印相应个数即可。

实现代码：

public String frequencySort(String s) {
    // 统计s中每种字符出现的次数
    Map<Character, Integer> map=new HashMap<>();
    for(char c : s.toCharArray()){
        int count = map.getOrDefault(c,0);
        map.put(c,count+1);
    }
    // 为了排序出现次数，将map转为PriorityQueue
    // queue中元素的排序规则为字符出现次数的降序排列
    PriorityQueue<Node> q=new PriorityQueue<>((a,b)->b.count-a.count);
    for(Character c : map.keySet()){
        q.offer(new Node(c, map.get(c)));
    }
    // 返回结果
    StringBuilder sb=new StringBuilder();
    while(q.size()>0){
        // 按顺序取出一个对象
        Node node=q.poll();
        // 循环该字符出现次数，并打印相应次数的该字符
        for(int i=0;i<node.count;i++) sb.append(node.c);
    }
    return sb.toString();
}

class Node{
    char c;
    int count;
    Node(char _c,int _count){
        c=_c;
        count=_count;
    }
}

本题解法执行时间为10ms。

Runtime: 10 ms, faster than 83.59% of Java online submissions for Sort Characters By Frequency.

Memory Usage: 40.5 MB, less than 11.11% of Java online submissions for Sort Characters By Frequency.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-451-sort-characters-by-frequency-解题思路分析/