以实际中并不经常使用
给定一个数组, 求如果排序之后, 相邻两数的最大差值, 要求时
间复杂度O(N), 且要求不能用非基于比较的排序。
public static int maxGap(int[] nums) {
if (nums == null && nums.length<2){
return 0;
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length;i++){
min = Math.min(nums[i],min);
max = Math.max(nums[i],max);
}
if (min == max) return 0;
int [] maxs = new int[nums.length+1];
int [] mins = new int[nums.length+1];
boolean[] hasNum = new boolean[nums.length+1];
for (int i = 0 ; i < nums.length ;i++){
int bid = bucket(nums[i],nums.length,min,max);
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],nums[i]):nums[i];
mins[bid] = hasNum[bid] ? Math.min(mins[bid],nums[i]):nums[i];
hasNum[bid] = true;
}
int lastMax = maxs[0];
int res = 0;
for (int i = 1;i<= nums.length ;i++){
if (hasNum[i]){
res = Math.max(res,mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。