无需数组排序后的最大相邻差
题目有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。
思绪
解法1：使用任意一种时间复杂度为O(nlogn)的排序算法(如快速排序)，给原数组排序，然后遍历排序号的数组，并对每队相邻元素求差，最终得到最大差值。该解法的时间复杂度是O(nlogn)，在不改变原数组的情况下，空间复杂度是O(n)。
解法2：
[*]1.使用计数排序的思想，先求出原数组的最大值max和最小值min的区间长度k(k=max-min+1)，以及偏移量d=min。
[*]2.创建一个长度为k的新数组Array。
[*]3.遍历原数组，每遍历一个元素，就把新数组Array对应下标的值+1。Array的值+1。遍历结束后，Array的一部分元素值变成了1或更高的数值，一部分元素值仍然是0。
[*]4.遍历新数组Array，统计出Array中最大的一连出现的0值得次数+1，即为相邻元素最大差值。
[*]5.这条思绪有限制，由于计数排序，只实用于正整数的排序。
解法3：
[*]1.使用桶排序的思想，根据原数组的长度n，创建出n+1个桶，注意是n+1桶，每一个桶代表一个区间范围。其中第1个桶从原数组的最小值min开始，区间跨度是(max -min)/n。
[*]2.遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大值和最小值。
[*]3.遍历所有的桶，，统计出每一个桶的最大值，和该桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。
注意，这里少了一个说明，为什么排序后最大的两个相邻元素的差，一定会是每一个桶的最大值，和该桶右侧非空桶的最小值的差，的最大值。
先从n个数，分到n+1个桶里，开始说明。第n+1个桶的区间，是，第1个桶的区间，是，d为前n个桶区间的差值。n个数，最小值，一定落在第一个桶里，最大值，一定在n+1个桶里，还有n-2个数，n-2个数，分散到n+1-2=n-1个桶里，则在这n-1个桶中，一定会由空桶，则相邻两个数的最大值的差值，一定出现在，最大一连空桶个数的左边第一个桶的最大值，和右边第一个桶的最小值。也可以说是每一个桶的最大值，和该桶右侧非空桶的最小值的差，数值最大的差。由于桶内，两个元素的最大差值，一定是小于区间差值d的。
将n+1桶，和并到第n个桶内，此时就是n桶就是[]的。此时n个数，分散到n个桶里，没有空桶最分散的情况，也就是每个桶里一个元素，两个相邻元素的最大差值也是，每一个桶的最大值，和该桶右侧非空桶的最小值的差，数值最大的差，假如出现空桶，和上面n+1个桶的情况就划一了。
所以，统计出每一个桶的最大值，和该桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。
代码
@SuppressWarnings("all")
public class MaxGroup {
public static int getMaxGroup(int[] array) {
int arrayLen = array.length;
if (arrayLen < 2)
return 0;
//1.得到数列的最大值和最小值
int max = array;
int min = array;
for (int i = 1; i < arrayLen; i++) {
if (max < array)
max = array;
if (min > array)
min = array;
}
int d = max - min;
if (d == 0)
return 0;
//2.初始化桶
int bucketNum = arrayLen;
Bucket[] buckets = new Bucket;
for (int i = 0; i < bucketNum; i++)
buckets = new Bucket();
//3.遍历原始数组，确定每个桶的最大最小值
for (int i = 0; i < arrayLen; i++) {
int index = ((array - min) / d * (bucketNum - 1));//求出当前元素，在整体区间的比值，再放大(len - 1)倍就是桶(所在区间)的索引 index + 1是桶的个数
if (buckets.getMin() == null || buckets.getMin() > array)
buckets.setMin(array);
if (buckets.getMax() == null || buckets.getMax() < array)
buckets.setMax(array);
}
//4.遍历桶，找到最大差值
int leftMax = buckets.getMax();
int maxGroup = 0;
for (int i = 1; i < bucketNum; i++) {
if (buckets.getMin() == null)
continue;//空桶跳过，如果桶非空，则该桶的min和max值，一定不为空
int differNum = buckets.getMin() - leftMax;
if (differNum > maxGroup)
maxGroup = differNum;
leftMax = buckets.getMax();//
}
return maxGroup;
}
private static class Bucket {
Integer min;
Integer max;
public Integer getMin() {
return min;
}
public void setMin(int min) {
this.min = min;
}
public Integer getMax() {
return max;
}
public void setMax(int max) {
this.max = max;
}
}
public static void main(String[] args) {
int[] array = new int[]{2, 5, 3, 4, 5, 10, 8};
System.out.println(getMaxGroup(array));
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]