LeetCode 笔记28 Maximum Gap

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

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

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

这道题题目有提示。

提示1 有线性时间复杂度解法

提示2 非负数，且强调32位整数

首先想排序的话，线性时间复杂度就那么几个解法，位图和基数排序。显然这个不能用位图，空间消耗太大。其实在看Algorithm 4th edition的时候就想，基数排序真是强大，完全可以用来做这个么。

不过当时我忘记基数排序的counting方法了。复习了一下才记起来。

public int maximumGap(int[] num) {
        if (num == null || num.length <= 1) {
            return 0;
        }

        for (int d = 0; d < 32; d++) {
            int[] count = new int[3];
            int[] aux = new int[num.length];
            for (int i = 0; i < num.length; i++) {
                count[((num[i] >> d) & 1) + 1]++;
            }

            for (int i = 1; i < 2; i++) {
                count[i] += count[i - 1];
            }

            for (int i = 0; i < num.length; i++) {
                aux[count[((num[i] >> d) & 1)]++] = num[i];
            }

            for (int i = 0; i < num.length; i++) {
                num[i] = aux[i];
            }
        }
        int maxGap = 0;
        for (int i = 1; i < num.length; i++) {
            if (num[i] - num[i - 1] > maxGap) {
                maxGap = num[i] - num[i - 1];
            }
        }
        return maxGap;
    }

count数组的意义具体可以参考上面提到的书关于String Sort的第一部分。

然后看了下leetcode的标准答案，原来用的桶排序。这个也很强大。

假设数组中最大元素是Max，最小元素Min，数组的长度是len，那么相邻两个数的平均间隔是D = (Max - Min)/(len - 1)。相邻两个数的最大间隔肯定大于等于这个数值。

那么我们不妨假设[Min, Max]之间所有数都可以放在紧紧排列的一个个桶中。每个桶的大小就是D。桶内元素是之间的间隔肯定不是要求的最大间隔，而是前一个桶中的最大值和后面一个桶的最小值才可能是最大间隔。我们遍历这样的值，就可以找出最大间隔。

桶的个数么，就是(Max - Min) / D + 1。

值为K的元素呢，就属于第(K - Min) / D 个桶里面了。

我们遍历一次数组，把每个桶都填上数组中的元素，同时可以求得每个桶的最大最小值。

再遍历一次桶，就求得了那个最大的间隔。

最后注意，如果len算出来是0，那么桶的个数就等于元素个数。

public int maximumGap2(int[] num) {
        if (num == null || num.length <= 1) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < num.length; i++) {
            if (num[i] > max) {
                max = num[i];
            }
            if (num[i] < min) {
                min = num[i];
            }
        }
        int len = (max - min) / (num.length - 1);
        if (len == 0) {
            len = 1;
        }
        int numOfBucket = (max - min) / len + 1;
        Bucket[] buckets = new Bucket[numOfBucket];
        for (int i = 0; i < num.length; i++) {
            int idx = (num[i] - min) / len;
            if (buckets[idx] == null) {
                buckets[idx] = new Bucket();
            }
            if (num[i] > buckets[idx].max) {
                buckets[idx].max = num[i];
            }
            if (num[i] < buckets[idx].min) {
                buckets[idx].min = num[i];
            }
        }
        int maxGap = 0;
        max = -1;
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                if (max == -1) {
                    //pass
                } else {
                    maxGap = Math.max(buckets[i].min - max, maxGap);
                }
                max = buckets[i].max;
            }
        }
        return maxGap;
    }

However，我发现桶排序做出来好像比基数排序慢也。