首页 > 代码库 > MAXIMUM GAP

MAXIMUM GAP

2024-08-09 20:05:57   216人阅读

博客已经搬家！请前往http://gqqnbig.me/?p=91 阅读本文。


题目

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（所有元素相同）到max?min。

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

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

MaxGap?Max?Minn?1

例如

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

这里把数组划分为虚拟的n-1组，设每组含头不含尾（除了最后一组），那么每组都划分到1个元素，即最小值（0）和最大值（10）之间的元素是均匀分布的。间隔都是105=2。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。

publicint maximumGap2(int[] num)
{
    if(num == null|| num.length < 2)
        return0;
 
    intmin = gqqnbig.util.Arrays.min(num);
    intmax = gqqnbig.util.Arrays.max(num);
 
    // the minimum possible gap, ceiling of the integer division
    intgap = (int) Math.ceil((double) (max - min) / (num.length - 1));
 
    List<Integer>[] blocks = bucketSort(num, num.length -1);
 
    // scan the buckets for the max gap
    intmaxGap = Integer.MIN_VALUE;
    intpreviousMax = min;
    for(inti = 0; i < blocks.length; i++)
    {
        if(blocks[i].isEmpty())
            continue;
 
        intbucketsMIN = Collections.min(blocks[i]);
        intbucketsMAX = 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);
    returnmaxGap;
}
 
/**
 * 用桶排序算法对arr数组排序，桶的数量由bucketCount指定。
 * <p>
 * 如果bucketCount等于max-min，则返回值退化为int[]； 否则每个桶可能含有多于一个元素。
 * </p>
 * 时间复杂度O(arr.length)，空间复杂度O(arr.length)。
 *
 * @param arr
 * @return
 */
publicstatic List<Integer>[] bucketSort(int[] arr,int bucketCount)
{
    List<Integer>[] buckets =new List[bucketCount];
    for(inti = 0; i < buckets.length; i++)
        buckets[i] =new LinkedList<Integer>();
 
    intmin = gqqnbig.util.Arrays.min(arr);
    intmax = gqqnbig.util.Arrays.max(arr);
    intgap = (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(inti = 0; i < arr.length; i++)
    {
        intbucketIndex = (arr[i] - min) / gap;
        if(bucketIndex == bucketCount) // 桶的范围算头不算尾，但最后一个桶要算尾。
            bucketIndex--;
        buckets[bucketIndex].add(arr[i]);
 
    }
    returnbuckets;
 
}

MAXIMUM GAP


联系
我们