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

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

• 题目
• 解题思路
• 代码

题目

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

解题思路

这个问题也是一个TOPK问题，只不过变成了统计char的个数。

用哈希表存储每个字符的出现次数，再通过一个大顶堆（根据出现次数排序），不断取出堆顶元素，使用StringBuilder不断append即可。

代码

class Solution {
  public String frequencySort(String s) {
        if (s == null) {
            return null;
        }
        //        首先统计不同的元素出现的次数。
        Map<Character,Integer> map=new HashMap<>();
        for(char  str:  s.toCharArray()){//toCharArray() 方法将字符串转换为字符数组。
            if (map.containsKey(str)){
                map.put(str,map.get(str)+1);//统计次数
            }else {
                map.put(str,1);
            }
        }

        //        遍历map，用大顶堆保存频率最大的K个元素
        PriorityQueue<Map.Entry<Character, Integer>> pq=new PriorityQueue<>( (e1, e2) -> e2.getValue() - e1.getValue());
        pq.addAll(map.entrySet());//将MAP中的每一个"K-V"对，作为一个元素存入到pq这个大顶堆

        StringBuilder SB=new StringBuilder();
        while (!pq.isEmpty()){
            Map.Entry<Character,Integer>  entry=pq.poll();//poll 方法每次从 PriorityQueue 的头部删除一个节点,并返回该值
            for (int i=0;i<entry.getValue();i++){//遍历刚刚弹出来的那个值
                SB.append(entry.getKey());
            }

        }
        return SB.toString();
    }

}