Leetcode刷题100天—451. 根据字符出现频率排序(优先队列)—day16

港控/mmm° 2022-09-11 01:20 159阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210823182940888][]

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

示例 1:

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

示例 2:

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

示例 3:

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

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

package 优先队列;
    
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.PriorityQueue;
    
    public class _451_根据字符出现频率排序 { 
    	public static String frequencySort(String s) { 
    // 设置返回的字符串
    		String str="";
    // 1. 通过哈希统计词频 2. 将value存入优先队列中进行排序 3. 最后遍历输出
    		
    		Map<Character, Integer> map=new HashMap<Character, Integer>();
    		for(int i=0;i<s.length();i++) { 
    			System.out.println(s.charAt(i));
    			map.put(s.charAt(i),map.getOrDefault(s.charAt(i), 0)+1);
    		}
    		System.out.println(map);//{r=1, t=1, e=2}
    // 设置优先队列，由于题目要求降序，所以使用大顶堆
    		PriorityQueue<str> queue=new PriorityQueue<>(new Comparator<str>() { 
    			public int compare(str o1,str o2) { 
    				return o2.getCount()-o1.getCount();//大顶堆
    			}
    		});
    // 通过for循环将对应的值入队
    		for(Map.Entry<Character, Integer> entry : map.entrySet()) { 
    			queue.offer(new str(entry.getKey(),entry.getValue()));
    		}
    		while(!queue.isEmpty()) { 
    			str+=queue.poll();
    			System.out.println(str);
    		}
    
    		return str;
    	}
    //创建一个数据类Data，包含一个char类型的字符和int类型的次数
    	public static class str{ 
    		char c;
    		int  num;
    // 构造函数
    		public str(char c ,int num) { 
    			// TODO 自动生成的构造函数存根
    			this.c=c;
    			this.num=num;
    		}
    		public char getC() { 
    			return this.c;
    		}
    		public int getCount() { 
    			return this.num;
    		}
    // 返回字符串
    		public String toString() { 
    // String str="";
    			StringBuilder str = new StringBuilder();
    			for (int i=0;i<num;i++) { 
    				str.append(c);
    			}
    			return str.toString();
    		}
    	}
    	public static void main(String args[]) { 
    		String s="tree";
    		String c=frequencySort(s);
    	}
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210823182940888]: /images/20220829/b389e872425f4ea5817ce6d13d971018.png