leetcode451

叁歲伎倆 2021-11-14 13:18 183阅读 0赞

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

示例 1:

输入:  
"tree"

输出:  
"eert"

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

输入:  
"cccaaa"

输出:  
"cccaaa"

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

学习：

*  一般套路，map存储，后进行桶排序
 *  往往不用int数组做桶，用List\[\] list = new ArrayList\[\]，做桶，情况更好处理

class Solution {
        public String frequencySort(String s) {
              Map<Character,Integer> map = new HashMap<>();
            for(char c:s.toCharArray()){
                map.put(c,map.getOrDefault(c,0)+1);
            }
            
            //map后，桶操作
            List<Character>[] list = new ArrayList[s.length()+1];
            //填入
            for(Character c:map.keySet()){
                 Integer integervalue = map.get(c);
                 int i = 0;
                   while(i < integervalue) {
                       if (list[integervalue] == null) {
                           list[integervalue] = new ArrayList<>();
                       }
                       list[integervalue].add(c);
                       i++;
                   }    
            }
            
            
            //Stringuilder
            StringBuilder stringBuilder = new StringBuilder();
            for(int i = list.length-1;i >=0;i-- ){
                for(int j = 0;list[i]!=null &&j< list[i].size();j++){
                    stringBuilder.append(list[i].get(j));
                }
                
            }
            return stringBuilder.toString();
        }
    }