-
Notifications
You must be signed in to change notification settings - Fork 0
/
164MaximumGap.java
43 lines (39 loc) · 1.64 KB
/
164MaximumGap.java
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
37
38
39
40
41
42
43
//using bucket sort, two bucket. One store array in order without the max value,
//and the other bucket store array in order withou the min value
public class Solution {
public int maximumGap(int[] nums) {
if(nums == null || nums.length < 2) return 0;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int res = Integer.MIN_VALUE;
//find min and max value in the array
for(int i = 0; i < nums.length; i++) {
if(nums[i] < min ) min = nums[i];
if(nums[i] > max ) max = nums[i];
}
//determine gap in bucket
int step = (int)Math.ceil((double)(max - min)/(nums.length - 1));
int[] bucketMin = new int[nums.length - 1];
int[] bucketMax = new int[nums.length - 1];
Arrays.fill(bucketMin, Integer.MAX_VALUE);
Arrays.fill(bucketMax, Integer.MIN_VALUE);
//put numbers into correspondent bucket in MIN/MAX array
for(int i = 0; i < nums.length; i++) {
if(nums[i] == min || nums[i] == max) continue;
else {
int index = (nums[i] - min)/step;
bucketMin[index] = Math.min(bucketMin[index], nums[i] );
bucketMax[index] = Math.max(bucketMax[index], nums[i] );
}
}
//find max gao
int prev = min;
for(int i = 0; i < nums.length - 1; i++) {
if(bucketMin[i] == Integer.MAX_VALUE && bucketMax[i] == Integer.MIN_VALUE) continue;
res = Math.max(res, bucketMin[i] - prev);
prev = bucketMax[i];
}
res = Math.max(res, max - prev);
return res;
}
}