给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度O(N),且要求不能用非基于比较的排序
程序员文章站
2024-03-15 22:38:30
...
解题思路
n个数,制造n+1个桶 找到空桶的左边的最大值,和右边的最小值 相减即结果
package lesson01;
import java.util.Arrays;
public class Code02_MaxGap {
// Core code
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(min, nums[i]); // 找出所有数组中最大和最小的数
max = Math.max(max, nums[i]);
}
if (min == max)
return 0;
boolean hasNum[] = new boolean[nums.length + 1]; // 标记当前数是否进入过该桶
int mins[] = new int[nums.length + 1]; // 当前桶只放两个数,当前范围的最大和最小值
int maxs[] = new int[nums.length + 1];
int bid = 0;
for (int i = 0; i < nums.length; i++) { // 更新当前桶的最大和最小值
bid = bucket(min, max, nums.length, nums[i]);
// 第一次 hasNum[bid] = false mins[bid] = nums[i]
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
int lastMax = maxs[0];
int res = 0;
int i = 1;
for (; i < hasNum.length; i++) { // 找到空桶的左边的最大值,和右边的最小值 即结果res
if (hasNum[i]) {
res = Math.max(res, (mins[i] - lastMax));
lastMax = maxs[i];
}
}
return res;
}
// Core code
public static int bucket(int min, int max, int len, int num) { // n个数,制造n+1个桶
return (num - min) * len / (max - min);
}
// help code
public static int comparator(int[] arr2) {
if (arr2 == null || arr2.length < 2)
return 0;
Arrays.sort(arr2);
int gap = Integer.MIN_VALUE;
for (int i = 0; i < arr2.length - 1; i++)
gap = Math.max(gap, (arr2[i + 1] - arr2[i]));
return gap;
}
// help code
public static int[] copyArray(int[] arr1) {
if (arr1 == null)
return null;
int temp[] = new int[arr1.length];
for (int i = 0; i < arr1.length; i++)
temp[i] = arr1[i];
return temp;
}
// help code
public static int[] generateRandomArray(int maxSize, int maxValue) {
int temp[] = new int[(int) (Math.random() * (maxSize + 1))];
for (int i = 0; i < temp.length; i++)
temp[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
return temp;
}
public static void main(String[] args) {
int testTime = 10000;
int maxSize = 20;
int maxValue = 20;
boolean flag = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (maxGap(arr1) != comparator(arr2)) {
flag = false;
break;
}
}
System.out.println(flag ? "Nice!" : "Error!");
}
}