欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度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!");

	}
}