[LeetCode]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.

题目大意:

给定一个未排序的数组,找出其排序后的序列中两个相邻元素之间的最大差值。

最好在线性时间、线性空间复杂度内完成。

如果数组少于2个元素,返回0

可以假设数组中的所有元素均为非负整数,并且在32位带符号整数的范围以内。

解题思路:

基数排序(radix sort)/桶排序(bucket sort)

官方版(桶排序):

假设有N个元素A到B。

那么最大差值不会小于ceiling[(B - A) / (N - 1)]

令bucket(桶)的大小len = ceiling[(B - A) / (N - 1)],则最多会有(B - A) / len + 1个桶

对于数组中的任意整数K,很容易通过算式loc = (K - A) / len找出其桶的位置,然后维护每一个桶的最大值和最小值

由于同一个桶内的元素之间的差值至多为len - 1,因此最终答案不会从同一个桶中选择。

对于每一个非空的桶p,找出下一个非空的桶q,则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。

官方版Python代码(Accepted 240ms):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
        N = len(num)
        if N < 2:
            return 0
        A = min(num)
        B = max(num)
        bucketRange = max(1, int((B - A - 1) / (N - 1)) + 1) #ceil( (B - A) / (N - 1) )
        bucketLen = (B - A) / bucketRange + 1
        buckets = [None] * bucketLen
        for K in num:
            loc = (K - A) / bucketRange
            bucket = buckets[loc]
            if bucket is None:
                bucket = {'min' : K, 'max' : K}
                buckets[loc] = bucket
            else:
                bucket['min'] = min(bucket['min'], K)
                bucket['max'] = max(bucket['max'], K)
        maxGap = 0
        for x in range(bucketLen):
            if buckets[x] is None:
                continue
            y = x + 1
            while y < bucketLen and buckets[y] is None:
                y += 1
            if y < bucketLen:
                maxGap = max(maxGap, buckets[y]['min'] - buckets[x]['max'])
            x = y
        return maxGap

上面的代码感谢jakwings的热心解答:https://oj.leetcode.com/discuss/18543/memory-limit-exceeded-my-python-code-got-a-mle

下面的代码由于使用了dict,超出了系统内存限制,导致(Memory Limit Exceeded),同时代码中也包含一些错误

class Solution:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
        N = len(num)
        if N < 2:
            return 0
        A = min(num)
        B = max(num)
        # FIXME might cause a ZeroDivisionError when A == B
        bucketRange = int((B - A - 1) / (N - 1)) + 1 #ceil( (B - A) / (N - 1) )
        bucketLen = (B - A) / bucketRange + 1
        buckets = {}
        for K in num:
            loc = (K - A) / bucketRange
            bucket = buckets.get(loc)
            if bucket is None:
                bucket = {'min' : K, 'max' : K}
                buckets[loc] = bucket
            else:
                bucket['min'] = min(bucket['min'], K)
                bucket['max'] = max(bucket['max'], K)
        maxGap = 0
        for x in range(bucketLen):
            if buckets.get(x) is None:
                continue
            y = x + 1
            while y < bucketLen and buckets.get(y) is None:
                y += 1
            if y < bucketLen:
                maxGap = max(maxGap, buckets[y]['min'] - buckets[x]['max'])
            x = y
        return maxGap

本人版本(基数排序):

令maxSize为最大值B的数字(字符串形式)的长度,按照数字的每一位,从低位到高位,将数字分配到其所属的0-9这10个桶中,重复执行maxSize次分配。

本人版本Python代码(Accepted 412ms):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
        if len(num) < 2:
            return 0
        strNum = []
        maxSize = 1
        # convert num to string list, work out max size of num
        for e in num:
            eStr = str(e)[::-1] # reversed string
            strNum.append(eStr)
            maxSize = max(maxSize, len(eStr))
        # radix sort
        for x in range(maxSize):
            buckets = [[] for y in range(10)]
            for e in strNum:
                if len(e) <= x:
                    buckets[0].append(e)
                else:
                    buckets[int(e[x])].append(e)
            strNum = []
            for y in range(10):
                strNum.extend(buckets[y])
        num = [int(x[::-1]) for x in strNum]
        maxGap = 0
        for x in range(len(num) - 1):
            maxGap = max(maxGap, num[x + 1] - num[x])
        return maxGap

O(nlogn)排序版本(Accepted 200ms):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
        num = sorted(num)
        maxGap = 0
        for x in range(len(num) - 1):
            maxGap = max(maxGap, num[x + 1] - num[x])
        return maxGap

p.s. 官方版本用Java语言可以通过,可见leetcode对Python的内存限制相对比较严苛

//Java源码,参阅:https://oj.leetcode.com/discuss/18499/bucket-sort-java-solution-with-explanation-o-time-and-space
public class Solution {
    public int maximumGap(int[] num) {
        if (num == null || num.length < 2)
            return 0;
        // get the max and min value of the array
        int min = num[0];
        int max = num[0];
        for (int i:num) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        // the minimum possibale gap, ceiling of the integer division
        int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
        int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
        int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket
        Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
        Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
        // put numbers into buckets
        for (int i:num) {
            if (i == min || i == max)
                continue;
            int idx = (i - min) / gap; // index of the right position in the buckets
            bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
            bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
        }
        // scan the buckets for the max gap
        int maxGap = Integer.MIN_VALUE;
        int previous = min;
        for (int i = 0; i < num.length - 1; i++) {
            if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
                // empty bucket
                continue;
            // min value minus the previous value is the current gap
            maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
            // update previous bucket value
            previous = bucketsMAX[i];
        }
        maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
        return maxGap;
    }
}

 

本文链接:http://bookshadow.com/weblog/2014/12/14/leetcode-maximum-gap/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. heavensyu求长肉 heavensyu求长肉 发布于 2014年12月29日 10:19 #

    “那么最大差值不会大于ceiling[(B - A) / (N - 1)]”,是不是翻译错了?应该是最大差值不会小于[(B - A) / (N - 1)]。

  2. 在线疯狂 在线疯狂 发布于 2014年12月29日 15:17 #

    是的,应该是不小于,多谢勘误!

  3. Miaoming Miaoming 发布于 2015年1月29日 04:56 #

    这个题有点莫名其妙啊。。。。bucket sort的话假如我就俩数字一个0一个99999999无限个9那岂不是内存要爆了?这题的核心意思到底是啥。。。

  4. 在线疯狂 在线疯狂 发布于 2015年1月29日 13:17 #

    这道题的意图应该就是考察线性时间排序

  5. 耳朵小没福 耳朵小没福 发布于 2015年2月9日 11:27 #

    有个问题,说明中是(B-A)/(N-1), 为什么代码里面是(B-A-1)/(N-1) + 1?

  6. 在线疯狂 在线疯狂 发布于 2015年2月9日 18:00 #

    int( ( B - A - 1 ) / ( N - 1 ) ) + 1的值等于( B - A ) / ( N - 1 )向上取整(ceil函数)

  7. qbuer qbuer 发布于 2016年1月3日 13:10 #

    我觉得这个题只是有桶这个概念,和桶排序没啥关系...

张贴您的评论