题目要求
1
2
3
4
5
6
7
| 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.
|
一个乱序的数组，找到其有序排列后相邻两个数之间最大的间隔。试着用线性时间和空间复杂度来解决这个问题。
思路和代码
这里并不需要完全的进行排序。我们只需要找到合适的区间划分，并将各个数字丢到其所属的区间中。之后，我们只需要比较前一个区间的最大值和后一个区间的最小值之间的差距即可以获得该数组最大的间隔。
这里选择区间划分的方式是找到这一组数字的“最小”间隔。这里最小的意思并不是说任意两个数之间的最小间隔，而是指这一组数字的最大间隔必然不小于这个最小间隔。
我们可以知道，假设有n个数字，那么这n个数字的最小间隔为Math.ceil((double)(max-min) / (count-1))，即将最大值和最小值的差距按照数组大小等分。
可以将其想象为爬楼梯，我们从最小的数字试图爬到最大的数字，一共有n-1级台阶，而且每个台阶的高度为整数。那么一旦有一级台阶比最小间隔矮，就必然有一级比最小间隔高，从而才能爬到最大的数字。
因此，我们现在相当于分出了n个桶，每个数字必然落入这n个桶中的一个。而每个桶内的数字间隔必然不会超过最小间隔。所以正如上文所说，比较相邻两个桶的边界就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public int maximumGap(int[] nums) {
int count = nums.length;
if(count < 2) return 0;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int num : nums){
min = Math.min(min, num);
max = Math.max(max, num);
}
int minGap = (int)Math.ceil((max - min) * 1.0 / (count - 1));
if(minGap==0) return minGap;
int[] minBucket = new int[count];
int[] maxBucket = new int[count];
for(int i = 0 ; i<count ; i++){
minBucket[i] = Integer.MAX_VALUE;
maxBucket[i] = Integer.MIN_VALUE;
}
for(int num : nums){
int index = (num - min) / minGap;
minBucket[index] = Math.min(minBucket[index], num);
maxBucket[index] = Math.max(maxBucket[index], num);
}
int prev = maxBucket[0];
int maxGap = minGap;
for(int i = 1 ; i<count ; i++){
if(minBucket[i] > maxBucket[i]) continue;
maxGap = Math.max(minBucket[i] - prev, maxGap);
prev = maxBucket[i];
}
return maxGap;
}
|