Description

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Notice

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Example

Given[1, 9, 2, 5], the sorted form of it is[1, 2, 5, 9], the maximum gap is between5and9=4.

Solution

1. 普通sort, O(nlogn)
2. Bucket sort, O(n) 定义合适的bucket的个数和大小？遍历一遍找到数组的min和max，得到最大最小数间的距离d=max-min,试图把d按照数组的长度n等分。size=d/n + 1, num = d/size + 1.之所以要+1是因为可能有零头
   max gap可能是后一个bucket的max-前一个bucket的min，也可能是同一个bucket的max-min,因此只要记录下来每个bucket的min和max即可。因为有的bucket可能一个数都没有，所以用一个hashset记录有值在里面的bucket的index。算maxgap的时候只遍历里面有值的bucket。
   maxGap应该从0 开始，因为只有一个数的数组，他的maxGap是0

public class Solution {
    /*
     * @param nums: an array of integers
     * @return: the maximun difference
     */
    public int maximumGap(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int min = nums[0];
        int max = nums[0];
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        int distance = max - min;
        if (distance == 0) {
            return 0;
        }

        int n = nums.length;
        int bucketSize = distance / n + 1;
        int bucketNum = distance / bucketSize + 1;

        int[] bucketMin = new int[bucketNum]; // store the min values of each bucket
        int[] bucketMax = new int[bucketNum]; // store the max values of each bucket
        HashSet<Integer> set = new HashSet<Integer>(); // use to store the buckets that have values in it.
        int maxGap = 0; // max gap should be initialized to 0 instead of MIN_VALUE
        for (int num : nums) {
            int index = (num - min) / bucketSize;
            if (!set.contains(index)) {
                bucketMin[index] = num;
                bucketMax[index] = num;
                set.add(index);
            } else {
                bucketMin[index] = Math.min(bucketMin[index], num);
                bucketMax[index] = Math.max(bucketMax[index], num);
                maxGap = Math.max(maxGap, bucketMax[index] - bucketMin[index]);
            }
        }

        // should consider weather the bucket contains values for calculating max gap.
        // the first bucket (index = 0) would definitely contains values, cause (min - min) / bucketNum = 0
        // so set pre-bucket to 0;
        int pre = 0;
        for (int i = 1; i < bucketNum; i++) {
            if (set.contains(i)) {
                maxGap = Math.max(maxGap, bucketMin[i] - bucketMax[pre]);
                pre = i;
            }
        }

        return maxGap;
    }
}