6.2

数组排序之后相邻数的最大差值

题目

给定一个整型数组arr，返回如果排序之后，相邻两数的最大差值。
arr=[9,3,1,10]。如果排序，结果为[1,3,9,10]，9和3的差为最大差值，故返回6。
arr=[5,5,5,5]。返回0。
如果arr的长度为N，请做到时间复杂度为O(N)。

思路

如果用排序做，最好的是O(n*log(n))
利用桶排的思想
比如有10个数，最小是10，最大是110，那么就化为11个区间，最后一个区间是最后一个数
其余区间就是[10,20),[20,30),[30,40)…[90,100),[100,110)
然后把这10个数字放到11个区间里去，那么必然有一个区间是空的
而最大差值是一个非空区间最大值与另一个非空区间最小值得差，(两者中间可能有空区间)
因为同一区间内的差值最大是就是间隔

因此需要先找到最大值和最小值，然后划分区间，把数字放到区间中去，找最大差值

代码

public int maxGap(int[] a) {
	if (a.length == 0 || a == null) {
		return 0;
	}
	// 求出最大最小值
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < a.length; i++) {
		min = Math.min(a[i], min);
		max = Math.max(a[i], max);
	}
	if (max == min) {
		// 最大值与最小值相等，说明所有数字都相等，差值为0
		return 0;
	}
	
	// 记录每个桶的最大值和最小值，及该桶是否有值
	int[] minb = new int[a.length + 1];
	int[] maxb = new int[a.length + 1];
	boolean[] is = new boolean[a.length + 1];
	
	int len = a.length;
	for (int i = 0; i < len; i++) {
		// 找到该数应该放在哪个桶里
		int bid = bucket(a[i], min, max, len);
		if (is[bid]) {
			minb[bid] = Math.min(a[i], minb[bid]);
			maxb[bid] = Math.max(a[i], maxb[bid]);
		} else {
			minb[bid] = a[i];
			maxb[bid] = a[i];
			is[bid] = true;
		}

	}

	
	int i = 0;
	//计算结果时候的前区间的最大值
	int num = 0;
	//最大差值，即后最小减前最大
	int res = 0;
	//找到第一个不空的区间
	while (i < len) {
		if (is[i]) {
			num = maxb[i];
			i++;
			break;
		}
	}
	//找到后面不空的区间
	for (; i <= len; i++) {
		if (is[i]) {
			res = Math.max(res, minb[i] - num);
			//每次重置前区间的最大值
			num = maxb[i];
		}
		
	}

	return res;

}

//找到数字i在哪个哪个区间中！
//((i - min) * len / (max - min))
//用long是为了防止溢出
public int bucket(long i, long min, long max, long len) {
	return (int) ((i - min) * len / (max - min));
}