来自https://oj.leetcode.com/problems/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.

分析

函数的值域是0（所有元素相同）到[latex]max-min[/latex]。

比较排序的时间复杂度是[latex]O(n\log n)[/latex]，而题目要求[latex]O(n)[/latex]。可用的排序算法有桶排序、计数排序、基数排序。

第二，假设数组中最小值是min，最大值是max，数组长度为n，则有

[latex]MaxGap \geqslant \frac{Max-Min}{n-1}[/latex]

例如

| 1| 1| 1| 1| 2|
x--x--x--x--x--x
|  |  |  |  |  |
0              10

这里把数组划分为虚拟的n-1组，设每组含头不含尾（除了最后一组），那么每组都划分到1个元素，即最小值（0）和最大值（10）之间的元素是均匀分布的。间隔都是[latex]\frac{10}{5}=2[/latex]。MaxGap=2。

如果有元素没有平均分布，

| 1| 0| 2| 1| 2|
x-----x-x-x--x-x
|  |  |  |  |  |
0              10

那么MaxGap就会大于2。同时可见第二组没有划分到元素，而第三组有2个元素。

把上面的均匀划分的组作为桶，应用桶排序的思想，把数组元素归到桶中。在一个桶内，元素差小于等于block.max-block.min。在两桶之间，元素差等于block2.min-block1.max。

[code lang=”java”]
public int maximumGap2(int[] num)
{
if (num == null || num.length < 2)
return 0;

int min = gqqnbig.util.Arrays.min(num);
int max = gqqnbig.util.Arrays.max(num);

// the minimum possible gap, ceiling of the integer division
int gap = (int) Math.ceil((double) (max – min) / (num.length – 1));

List<Integer>[] blocks = bucketSort(num, num.length – 1);

// scan the buckets for the max gap
int maxGap = Integer.MIN_VALUE;
int previousMax = min;
for (int i = 0; i < blocks.length; i++)
{
if (blocks[i].isEmpty())
continue;

int bucketsMIN = Collections.min(blocks[i]);
int bucketsMAX = Collections.max(blocks[i]);
maxGap = gqqnbig.Math.max(maxGap, bucketsMAX – bucketsMIN, bucketsMIN – previousMax);
// update previous bucket value
previousMax = bucketsMAX;
}
maxGap = Math.max(maxGap, max – previousMax);
return maxGap;
}

/**
* 用桶排序算法对arr数组排序，桶的数量由bucketCount指定。
* <p>
* 如果bucketCount等于max-min，则返回值退化为int[]； 否则每个桶可能含有多于一个元素。
* </p>
* 时间复杂度O(arr.length)，空间复杂度O(arr.length)。
*
* @param arr
* @return
*/
public static List<Integer>[] bucketSort(int[] arr, int bucketCount)
{
List<Integer>[] buckets = new List[bucketCount];
for (int i = 0; i < buckets.length; i++)
buckets[i] = new LinkedList<Integer>();

int min = gqqnbig.util.Arrays.min(arr);
int max = gqqnbig.util.Arrays.max(arr);
int gap = (int) Math.ceil((max – min) / (double) bucketCount);

// 桶的范围是
// [min, min+gap), [min+gap， min+2gap), … [min+(bucketCount-1)*gap, min+bucketCount*gap]
// min+bucketCount*gap>=max

for (int i = 0; i < arr.length; i++)
{
int bucketIndex = (arr[i] – min) / gap;
if (bucketIndex == bucketCount) // 桶的范围算头不算尾，但最后一个桶要算尾。
bucketIndex–;
buckets[bucketIndex].add(arr[i]);

}
return buckets;

}
[/code]