MaximumGap-桶排序-最大间隔问题

import java.util.Arrays;

public class MaximumGap {

	// 桶排序-相邻最大值
	public static int maximumGap(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int len = arr.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < len; i++) {
			min = Math.min(min, arr[i]);
			max = Math.max(max, arr[i]);
		}
		if (min == max) {
			return 0;
		}
		boolean book[] = new boolean[len + 1];
		int maxs[] = new int[len + 1];
		int mins[] = new int[len + 1];
		int id = 0;
		for (int i = 0; i < len; i++) {
			// 划分桶号，这里还是有点晕……
			id = (int) ((arr[i] - min) * len / (max - min));
			mins[id] = book[id] ? Math.min(mins[id], arr[i]) : arr[i];
			maxs[id] = book[id] ? Math.max(maxs[id], arr[i]) : arr[i];
			book[id] = true;
		}
		int res = 0;
		// 第一个桶内默认是最小值
		int lastMax = maxs[0];
		int i = 1;
		for (; i <= len; i++) {
			if (book[i]) {
				// 两个相邻的非空桶，后一个的最小值减去前一个的最大值为相对间隔最大值
				res = Math.max(res, mins[i] - lastMax);
				// 当前桶的最大值更新为前一个最大值
				lastMax = maxs[i];
			}
		}
		return res;

	}
	/*
	 * public static int scope(int arri, int len, int min, int max) { return (int)
	 * ((arri - min) * len / (max - min)); }
	 */

	// 调用系统类库函数
	public static int comparator(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		Arrays.sort(arr);
		int gap = Integer.MIN_VALUE;
		for (int i = 1; i < arr.length; i++) {
			gap = Math.max(arr[i] - arr[i - 1], gap);
		}
		return gap;
	}

	// 获取随机数组
	public static int[] getRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			// 获取 -maxVlaue + 1 ~ maxValue 的值
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}

		return arr;

	}

	// 复制数组
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] book = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			book[i] = arr[i];
		}
		return book;
	}

	public static void main(String[] args) {
		// 测试次数
		int test = 50000;

		// 数组长度
		int maxSize = 100;

		// 最大数值
		int maxValue = 100;
		boolean flag = true;
		for (int i = 0; i < test; i++) {
			int arr1[] = getRandomArray(maxSize, maxValue);
			// 拷贝比较
			int arr2[] = copyArray(arr1);
			if (maximumGap(arr1) != comparator(arr2)) {
				flag = false;
				break;
			}

		}
		System.out.println(flag ? "测试正常" : "发生错误");

		// 随机测试一组数据
		int arr[] = getRandomArray(maxSize, maxValue);
		System.out.println(Arrays.toString(arr));
		int t = maximumGap(arr);
		System.out.println(t);

	}

}