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(); } }