# 0451. Sort Characters By Frequency
###### tags: `Leetcode` `Bloomberg` `Medium` `Bucket Sort`
Link: https://leetcode.com/problems/sort-characters-by-frequency/
## 思路
### 思路一 O(NlogN) O(N)
用hashmap存 然后排序~
**注意排序那里的写法**
### 思路二 O(N) O(N)
桶排序
因为我们只需要知道每个frequency有哪几个字母并且我们知道最高的频率就是字符串的长度，因此可以使用桶排序
## Code
### 思路一

class Solution {
    public String frequencySort(String s) {
        Map<Character,Integer> map = new HashMap<>();
        char[] charArray = s.toCharArray();
        for(char c:charArray){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        List<Character> l = new ArrayList<>(map.keySet());
        Collections.sort(l,(a,b)->map.get(b)-map.get(a));
        
        StringBuilder sb = new StringBuilder();
        for(char c:l){
            int num = map.get(c);
            for(int i = 0;i < num;i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

### 思路二

class Solution {
    public String frequencySort(String s) {
        Map<Character,Integer> map = new HashMap<>();
        char[] charArray = s.toCharArray();
        for(char c:charArray){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        
        List<List<Character>> freq = new ArrayList<>();
        for(int i = 0;i < s.length();i++){
            freq.add(new ArrayList<Character>());
        }
        
        for(char c:map.keySet()){
            freq.get(map.get(c)-1).add(c);
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = s.length()-1;i>=0;i--){
            for(char c:freq.get(i)){
                for(int j = 0;j <= i;j++){
                    sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}