Bucket Sort

347. Top K Frequent Elements

bucket stores the element with the same frequency appearance. Each element in the bucket is null.

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k){
        int len = nums.length;
        List<Integer> res = new ArrayList<Integer>();
        //Find the frequency of each element
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: nums){
            if(!map.containsKey(num))
                map.put(num, 1);
            else
                map.put(num, map.get(num)+1);
        }

        ArrayList<Integer>[] bucket = new ArrayList[len+1];
        for(int element:map.keySet()){
            int frq = map.get(element);
            if(bucket[frq] == null){
                bucket[frq] = new ArrayList();
            }
            bucket[frq].add(element);
        }
        //swipe from the end to start 
        for(int i = len;i >= 0 && res.size() < k;i--){
            if(bucket[i] != null){
               res.addAll(bucket[i]);
            }
       }
       return res;
    }
}

164. Maximum Gap

考察Bucket Sort O(N)的方法为什么不是直接用Bucket 因为会有为0的element 而且总长度会很大 不如设置bucket的长度为原来数组的长度 然后将元素依次放入每个空格中 记录每个空格的min和max (min1,max1),(min2,max2) .... 然后依次取上一个元素的max1和下一个元素的min2比较 最后获得最大差值 很巧妙的解法

public int maximumGap(int[] num) {
    if(num == null || num.length < 2){
        return 0;
    }
    int max = num[0];
    int min = num[0];
    for(int i = 1; i < num.length; i++){
        max = Math.max(max, num[i]);
        min = Math.min(min, num[i]);
    }

    // initialize an array of buckets
    Bucket[] buckets = new Bucket[num.length + 1]; //project to (0 - n)
    for(int i = 0; i < buckets.length; i++){
        buckets[i] = new Bucket();
    }

    double interval = (double) num.length / (max - min);
    //distribute every number to a bucket array
    for(int i = 0; i < num.length; i++){
        int index = (int) ((num[i] - min) * interval);

        if(buckets[index].low == -1){
            buckets[index].low = num[i];
            buckets[index].high = num[i];
        }else{
            buckets[index].low = Math.min(buckets[index].low, num[i]);
            buckets[index].high = Math.max(buckets[index].high, num[i]);
        }
    }

    //scan buckets to find maximum gap
    int result = 0;
    int prev = buckets[0].high;
    for(int i = 1 ; i < buckets.length; i++){
        if(buckets[i].low != -1){
            result = Math.max(result, buckets[i].low - prev);
            prev = buckets[i].high;
        }
    }

    return result;
}

242. Valid Anagram

use the bucket to store each character's appereance time in Array A and check in array B. Then return true if there is an item whose bucket value is not 0

274. H-Index

we use n bucket to store the appearance of each items and sweep from the end to start

https://discuss.leetcode.com/topic/40765/java-bucket-sort-o-n-solution-with-detail-explanation/2

Time : O(N)

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] buckets = new int[n+1];
    for(int c : citations) {
        if(c >= n) {
            buckets[n]++;
        } else {
            buckets[c]++;
        }
    }
    int count = 0;
    for(int i = n; i >= 0; i--) {
        count += buckets[i];
        if(count >= i) {
            return i;
        }
    }
    return 0;
}

1057 Campus Bikes

see the video for explanation, this problem can be also solved by using heap sort

key insight of when you should use bucket sort when the possible largest value is finite (limit value)