桶排序

先用HashMap统计每个元素出现的频率，然后设置若干个桶，桶的下标代表每个元素出现的频率，把出现频率相同的元素添加到同一个桶中，下标为i代表桶中元素出现i次，再根据题目要求进行统计。

LeetCode对应题目：
347. Top K Frequent Elements (Medium)
348. Sort Characters By Frequency (Medium)

347 Top K Frequent Elements (Medium)
输入： [1,1,1,2,2,3] ，k = 2, 输出：[1,2].

public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int num:nums)
            map.put(num,map.getOrDefault(num,0)+1);
        List<Integer>[] fres = new ArrayList[nums.length+1];
        for(int key:map.keySet()){
            int fre = map.get(key);
            if(fres[fre]==null)
                fres[fre] = new ArrayList<Integer>();
            fres[fre].add(key);
        }
        List<Integer> ans = new ArrayList<Integer>();
        for(int i = fres.length-1;i>=0&&ans.size()<k;i--){
            if(fres[i]!=null)
             ans.addAll(fres[i]);
        }
        return ans;
    }

451 Sort Characters By Frequency (Medium)
要求：出现频率高的放在前面
输入：“tree”
输出：“eert”

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