根据字符出现频率排序

柔光的暖阳◎ 2024-04-06 12:35 62阅读 0赞

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

> 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。  
> 返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

##### 示例 1: #####

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

##### 示例 2: #####

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

##### 示例 3: #####

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

##### 提示: #####

*  1 <= s.length <= 5 \* 105
 *  s 由大小写英文字母和数字组成

#### 思路: ####

##### 桶排序 #####

由于每个字符在字符串中出现的频率存在上限，因此可以使用桶排序的思想，根据出现次数生成排序后的字符串。具体做法如下：

1.  遍历字符串，统计每个字符出现的频率，每个字符的频率上线为字符串的长度n；
2.  创建桶，存储从 1 到n 的每个出现频率的字符；
3.  按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符，然后将每个字符按照出现频率拼接到排序后的字符串。

#### 代码： ####

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class char_Fre {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		String s = "Aabb";
    		System.out.println(frequencySort(s));
    	}
    	public static String frequencySort(String s) {
        
    		Map<Character, Integer> fre = new HashMap<>();
    		for(char c : s.toCharArray()) {
        //将每一个字符以及出现的次数存到HashMap中
    			fre.put(c, fre.getOrDefault(c, 0) + 1);
    		}
    		List<Character> [] freBucket = new ArrayList[s.length()+1];//定义最大下标等于字母总个数，即n+1个桶
    		for(char c: fre.keySet()) {
        //把每个字符出现的个数当做数组的下标，存入到桶中
    			int f = fre.get(c);
    			if(freBucket[f] == null) {
        
    				freBucket[f] = new ArrayList<>();//动态数组
    			}
    			freBucket[f].add(c);
    		}
    		StringBuilder str = new StringBuilder();
    		for(int i = freBucket.length-1; i>=0; i--) {
        //按数组下标从大到小，即字母出现的频率由大到小依次存入到字符串中
    			if(freBucket[i] == null) {
        
    				continue;
    			}
    			for(char c: freBucket[i]) {
        
    				for(int j=0; j<i; j++) {
        
    					str.append(c);
    				}
    			}
    		}
    		return str.toString();
        }
    }

来源：[力扣（LeetCode）][LeetCode]  
注：仅供学习参考！

[LeetCode]: https://leetcode.cn/problems/sort-characters-by-frequency