## 题目描述：

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.

## 解题思路：

### 官方版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
``````

### 下面的代码由于使用了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``````

### 本人版本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))
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;
}
}
``````

Pingbacks已关闭。

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

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

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

是的，应该是不小于，多谢勘误！

3. 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 发布于 2016年1月3日 13:10 #

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