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. Implementation
(1) Sort
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < nums.length - 1; i++) {
res = Math.max(res, nums[i + 1] - nums[i]);
}
return res;
}
}
(2) Bucket Sort
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
if (min == max) {
return 0;
}
Bucket buckets[] = new Bucket[n];
for (int i = 0; i < n; i++) {
buckets[i] = new Bucket();
}
int bucketLen = (int)Math.ceil((double)(max - min) / (n - 1));
for (int num : nums) {
int index = (num - min)/bucketLen;
if (buckets[index].min == Integer.MAX_VALUE) {
buckets[index].min = num;
buckets[index].max = num;
}
else {
buckets[index].min = Math.min(buckets[index].min, num);
buckets[index].max = Math.max(buckets[index].max, num);
}
}
int maxGap = 0, prev = 0;
for (int i = 1; i < n; i++) {
if (buckets[i].min != Integer.MAX_VALUE) {
maxGap = Math.max(maxGap, buckets[i].min - buckets[prev].max);
prev = i;
}
}
return maxGap;
}
class Bucket {
int min, max;
public Bucket() {
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
}
}
}