每日算法之借助标准库解题（II）

这次继续学习使用标准库里的数据结构来解题

Q:Given a string, sort it in decreasing order based on the frequency of characters.

翻译君:一个字符串，按字符出现的次数由多到少重新排序这个字符串。

例如：

Input:
"tree"

Output:
"eert"

这题需要统计字符出现的次数，所以我们可以用HashMap这一数据结构。它的key表示字符，value表示该字符在字符串中出现的次数。

下面是解答这题的流程

1.准备一个Hashmap容器，存储字符对应的出现次数

2.遍历字符串统计字符的出现次数

          HashMap<Character, Integer> record=new HashMap<>();
          for(char c:s.toCharArray()){
              if(record.containsKey(c))
                  record.put(c, record.get(c)+1);
              else
                  record.put(c,1);
          }

3.下一步我们就需要借助桶数组。
数组桶的目的是将出现次数相同的字符放在一个桶里，这样我们最后就可以根据桶来依次取出字符出现频率由高到低的元素了。

        //3.准备若干桶，次数相同的字符装在一个桶里
          List<Character>[] bucket=new List[s.length()+1];
          for(char key:record.keySet()){
              int freq=record.get(key);
              if (bucket[freq]==null) {
                bucket[freq]=new ArrayList<>();
            }
              bucket[freq].add(key);
          }

4.因为桶是用数组集合存储，这样我们数组的下标就表示某个字符出现的频率。所以最后我对这个集合从后往前遍历，依次取出字符(乘以频率）再通过StringBuilder拼装，结果就是一串字符频率由高到低的字符串了。

 StringBuilder sb=new StringBuilder();
          for(int pos=bucket.length-1;pos>=0;pos--){
              if (bucket[pos]!=null) {
                  for(char c:bucket[pos]){
                     for(int i=0;i<pos;i++)
                         sb.append(c);
                  }
            }  
          }

完整代码如下:

public String frequencySort(String s) {
          //1.准备一个hashmap容器，存储字符以及对应出现的次数
          HashMap<Character, Integer> record=new HashMap<>();
          //2.把字符和对应字符出现次数加到hashmap中
          for(char c:s.toCharArray()){
              if(record.containsKey(c))
                  record.put(c, record.get(c)+1);
              else
                  record.put(c,1);
          }
          
         //3.准备若干桶，次数相同的字符装在一个桶里
          List<Character>[] bucket=new List[s.length()+1];
          for(char key:record.keySet()){
              int freq=record.get(key);
              if (bucket[freq]==null) {
                bucket[freq]=new ArrayList<>();
            }
              bucket[freq].add(key);
          }
          
          
          //4.依次取出字符并封装
          StringBuilder sb=new StringBuilder();
          for(int pos=bucket.length-1;pos>=0;pos--){
              if (bucket[pos]!=null) {
                  for(char c:bucket[pos]){
                     for(int i=0;i<pos;i++)
                         sb.append(c);
                  }
            }  
          }
          
          return sb.toString();
              
      }