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.
Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.
解题思路：
由于要用到线性时间复杂度，比较排序已经不适用了(《算法导论》P108)，能够用到的有 计数排序、基数排序、堆排序，由于计数排序比较适合小范围的，基数排序最终会将顺序排好，而我们不需要那么复杂，因此，可以用桶排序，适当选择桶之间的距离，保证最大的successive distance在两桶之间即可，JAVA实现如下：
public int maximumGap(int[] nums) {
if (nums.length <= 1)
return 0;
int min = nums[0], max = nums[0];
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
if (max == min)
return 0;
int distance = Math.max(1, (max - min) / (nums.length - 1));
int bucket[][] = new int[(max - min) / distance + 1][2];
for (int i = 0; i < bucket.length; i++) {
bucket[i][0] = Integer.MAX_VALUE;
bucket[i][1] = -1;
}
for (int num : nums) {
int i = (num - min) / distance;
bucket[i][0] = Math.min(num, bucket[i][0]);
bucket[i][1] = Math.max(num, bucket[i][1]);
}
int maxDistance = 1, left = -1, right = -1;
for (int i = 0; i < bucket.length; i++) {
if (bucket[i][1] == -1)
continue;
if (right == -1) {
right = bucket[i][1];
continue;
}
left = bucket[i][0];
maxDistance=Math.max(maxDistance, left-right);
right=bucket[i][1];
}
return maxDistance;
}