Bucket Sort

这个算法是要花费O(n) 的空间，平均复杂度为O(n) ，需要注意的是如何找到属于自己的Bucket Sort

1. 确定该数列的最大值和最小值，来确定要用多少个Bucket来装
2. 来把每个数字放到属于自己的Bucket，这里的公式比较重要
3. 最后把每个Bucket里面的排序

Color Sort

只有0, 1, 2 三种颜色那么就可以用三个Bucket来装，也就是最基本的Bucket Sort的思维，都不用在Bucket 里面再排，但是这里更好的one pass的替换法，与partition相似

public void sortColors(int[] nums) {
    int[] bucket = new int[3];
    for (int i = 0; i < nums.length; i++) bucket[nums[i]]++;
    for (int i = 0, index = 0; i < 3; i++) {
         for (int j = 0; j < bucket[i]; j++) {
             nums[index++] = i;
         }
     }
 }

 public void sortColors(int[] nums) {
    int l = 0, r = nums.length - 1;
    for (int i = l; i <= r; ++i) {
        if (nums[i] == 0) {
            swap(nums, i, l++);     //
        } 
        if (nums[i] == 2) {
            swap(nums, i--, r--);   // i should back to previous position, crz we dont kown current value
        }
    }
}
private void swap(int[] nums, int l, int r) {
  if (nums[l] == nums[r]) return;
  nums[l] ^= nums[r];
  nums[r] ^= nums[l];
  nums[l] ^= nums[r];
}

Maximum Gap

在Follow up 里面要求Linear Time and Space，那么就要想到是Bucket Sort的思维，思路并不难。主要难点在于，如何找到准确的Bucket。

1. 先找到该数组最大值max，最小值min，按照多大的gap来分割 gap = (max - min - 1) / (nums.length - 1) + 1
2. 初始化两个重要的数组，BucketMAX(当前Bucket里面的的最大值)，BucketMIN(当前Bucket里面的最小值)
3. 循环一遍每个在数组里面的值 m 对应的Bucket 应该是：int index = (m - min) / gap
4. 那么在这一层的循环里面就把BucketMAX 和BucketMIN 全部搞定
5. maxgap 就是找相邻的Bucket 的最大值和最小值的差。其中的最大值即为结果

Top K Frequent Elements

一共有3种解法，这里不论哪一种都是要用map来记录出现的频率

1. Heap

   可以用出现的频率来进行排序。这里比较特殊的是在heap里面装的是Map.Entry<T1, T2>

2. TreeMap

   算法思维上面是和Bucket Sort的想法一样：TreeMap<Frequent, List<Numbers>>，但是这里的一些TreeMap的操作要知道:

   1. addAll(List<Integere>)
   2. pollLastEntry

3. Bucket Sort

public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int n: nums){
        map.put(n, map.getOrDefault(n,0)+1);
    }

    TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
    for(int num : map.keySet()){
       int freq = map.get(num);
       if(!freqMap.containsKey(freq)){
           freqMap.put(freq, new LinkedList<>());
       }
       freqMap.get(freq).add(num);
    }

    List<Integer> res = new ArrayList<>();
    while(res.size()<k){
        Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
        res.addAll(entry.getValue());
    }
    return res;
}

Sort Characters By Frequency

跟上题一摸一样 ， 用Bucket 来实现

public String frequencySort(String s) {
    StringBuilder res = new StringBuilder();
    Map<Character, Integer> count = new HashMap<>();
    for (char c : s.toCharArray()) count.put(c, count.containsKey(c) ? count.get(c) + 1 : 1);

    List<Character>[] bucket = new List[s.length() + 1]; // how to initialize? + 1？
    for (char c : count.keySet()) {
        int freq = count.get(c);
        if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
        bucket[freq].add(c);
    }

    for (int i = bucket.length - 1; i >= 0; i--) {
        if (bucket[i] == null) continue;
        for (char c : bucket[i]) {
            for (int j = 0; j < i; j++) res.append(c);
        }
    }
    return res.toString();
}