无需数组排序后的最大相邻差

题目

有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。
思绪

解法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[n-min]的值+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个桶的区间，是[max,max]，第1个桶的区间，是[min,min+d]，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个桶的情况就划一了。
所以，统计出每一个桶的最大值，和该桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。
代码

1. @SuppressWarnings("all")
2. public class MaxGroup {
4.     public static int getMaxGroup(int[] array) {
5.         int arrayLen = array.length;
6.         if (arrayLen < 2)
7.             return 0;
8.         //1.得到数列的最大值和最小值
9.         int max = array[0];
10.         int min = array[0];
11.         for (int i = 1; i < arrayLen; i++) {
12.             if (max < array[i])
13.                 max = array[i];
14.             if (min > array[i])
15.                 min = array[i];
16.         }
17.         int d = max - min;
18.         if (d == 0)
19.             return 0;
20.         //2.初始化桶
21.         int bucketNum = arrayLen;
22.         Bucket[] buckets = new Bucket[bucketNum];
23.         for (int i = 0; i < bucketNum; i++)
24.             buckets[i] = new Bucket();
26.         //3.遍历原始数组，确定每个桶的最大最小值
27.         for (int i = 0; i < arrayLen; i++) {
28.             int index = ((array[i] - min) / d * (bucketNum - 1));//求出当前元素，在整体区间的比值，再放大(len - 1)倍就是桶(所在区间)的索引 index + 1是桶的个数
29.             if (buckets[index].getMin() == null || buckets[index].getMin() > array[i])
30.                 buckets[index].setMin(array[i]);
31.             if (buckets[index].getMax() == null || buckets[index].getMax() < array[i])
32.                 buckets[index].setMax(array[i]);
33.         }
35.         //4.遍历桶，找到最大差值
36.         int leftMax = buckets[0].getMax();
37.         int maxGroup = 0;
38.         for (int i = 1; i < bucketNum; i++) {
39.             if (buckets[i].getMin() == null)
40.                 continue;//空桶跳过，如果桶非空，则该桶的min和max值，一定不为空
41.             int differNum = buckets[i].getMin() - leftMax;
42.             if (differNum > maxGroup)
43.                 maxGroup = differNum;
44.             leftMax = buckets[i].getMax();//
45.         }
46.         return maxGroup;
47.     }
49.     private static class Bucket {
50.         Integer min;
51.         Integer max;
53.         public Integer getMin() {
54.             return min;
55.         }
57.         public void setMin(int min) {
58.             this.min = min;
59.         }
61.         public Integer getMax() {
62.             return max;
63.         }
65.         public void setMax(int max) {
66.             this.max = max;
67.         }
68.     }
70.     public static void main(String[] args) {
71.         int[] array = new int[]{2, 5, 3, 4, 5, 10, 8};
72.         System.out.println(getMaxGroup(array));
74.     }
76. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。