Bucket Sort

Top K Frequent elements

这题用 bucket sort只是取个巧，实现面试肯定会指出消耗太多空间的问题 所以还是应该掌握到using heap的方法

Contain Duplicates III

Maximum Gap

• 这题真正在考会不会写radix sort，只是也可以用Bucket sort来优化

• 这题的意思就是给你一个unsorted array,求sort之后任意两个数之间的最大差

• brute force的做法就是先排序，然后挨个找difference,O(NLogN)时间解决

  public int maximumGap(int[] nums) {
        //brute force sort and find diff
        //O(NLogN)
        if(nums == null || nums.length < 2) return 0;
        Arrays.sort(nums);
        int res = 0;
        for(int i = 1 ; i< nums.length; i++){
            int diff = nums[i] - nums[i-1];
            res = Math.max(res, diff);
        }
        return res;
    }

• 但明显不符合O(N)的要求，于是自然想到，什么排序方法能实现O（N）呢？Bucket Sort, Radix Sort还是Counting Sort?

• 于是乎看了Dicuss里帖子，自己照着思路调了1小时才bug free，看起来算法简单，其实写起来还是有点难度的，各种corner case

public int maximumGap(int[] nums) {
        //using bucket sort
        //min: minimum number of array
        //max: maximum number of array
        //THINK OF IT: since the max difference must not be smaller than ceiling[(max - min)/(N-1)]
        //so we can construct N-1 bucket, the gap is ceiling[(max-min)/(N-1)]

        //be aware of this case [1,1000]
        //这个例子说明了max不一定能在bucket里面，可能刚好是边界
        if (nums == null || nums.length < 2) return 0;
        int n = nums.length;
        //find global max and min of array
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int num : nums){
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        //gao between two buckets
        int gap = (int)Math.ceil((double)(max-min)/(n -1));
        //construct two buckets to store the max and min of every bucket
        int[] bucket_min = new int[n - 1];//bucket numer should be n - 1
        int[] bucket_max = new int[n - 1];
        //不能Arrays.fill(bucket_min, max); case: [3,6,9,1]
        Arrays.fill(bucket_min, Integer.MAX_VALUE);
        Arrays.fill(bucket_max, Integer.MIN_VALUE);
        //find the max and min of every bucket
        for(int num : nums){
            if(num == max) continue;
            int idx = (num - min)/gap;
            bucket_min[idx] = Math.min(num, bucket_min[idx]);
            bucket_max[idx] = Math.max(num, bucket_max[idx]);
        }

        int prev_max = min;
        int maxGap = 0;
        for(int i = 0; i < n - 1; i++){
            //empty bucket
            if(bucket_min[i] == Integer.MAX_VALUE && bucket_max[i] == Integer.MIN_VALUE){
                continue;
            }
            //gap = min number of bucket[i] - max number of bucket[i-1]
            maxGap = Math.max(maxGap,bucket_min[i] - prev_max);
            prev_max = bucket_max[i];
        }
        //be aware of this case [1,1000]
        //这个例子说明了max不一定能在bucket里面，可能刚好是边界
        //所以需要再check 一次
        maxGap = Math.max(maxGap, max - prev_max);
        return maxGap;
    }

• 其实这题用Radix sort更简单，可以写一个Radix sort array的method

• sort完之后直接扫一遍得出maxGap,代码比Bucket Sort的要好写很多

  public int maximumGap(int[] nums) {
        if(nums == null || nums.length < 2) return 0;
        int n = nums.length;
        int[] sorted_nums = new int[n];
        int bits = 10;//Integer.MAX_VALUE at most has 10 bits
        //find the max number
        int max = -1;
        for(int num : nums){
            max = Math.max(max, num);
        }
  
        int exp = 1;
        while(max / exp > 0){
            int[] counts = new int[10];//total count of num i 
            //数0,1,2,3,4～9的数分别出现的次数
            for(int i = 0; i < n; i++){
                counts[nums[i]/exp % 10]++;
            }
            //increment the total count
            for(int i = 1; i < 10; i++){
                counts[i] += counts[i-1];
            }
            //从后往前根据counts[]把nums[i]放在相应的位置，注意先--counts[]
            for(int i = n - 1; i >= 0; i--){
                sorted_nums[--counts[nums[i]/exp%10]] = nums[i];
            }    
            //assign sorted_nums to nums
            for(int i = 0; i< n; i++){
                nums[i] = sorted_nums[i];
            }
            exp *= 10;
        }
        int maxGap = 0;
        //now the nums has been sorted
        for(int i = 1; i < n; i++){
            maxGap = Math.max(maxGap, nums[i] - nums[i-1]);
        }
        return maxGap;
    }
  }