数据结构和算法（刷题） - 无序数组排序后的最大相邻差

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

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

三种方法：

1. 排序后计算比较

   • 简介：用任意一种时间复杂度为 $O(n\log n)$ 的排序算法给原数组排好序。然后遍历排序好的数组，并对每两个相邻元素求差，最终得到最大差值。
   • 思考：时间复杂度为$O(n\log n)$，在不改变原数组的情况下，空间复杂度为$O(n)$（存储排序好的数组）。但这道题显然不是用来排序的。

2. 利用计数排序的思想

   • 简介：求出原数组的最大最小值max和min，区间长度k=max - min +1，偏移量 min。创建一个长度为k的数组。遍历原数组，若原数组值为n，则array[n-min]的值加1。遍历新数组，统计最大连续出现0值的次数+1，就是相邻元素的最大差值。
   • 思考：若原数组是 1， 10000003，10000006 这三个元素呢，没办法了，想到了桶排序好像可以解决这个问题

3. 利用桶排序的思想

   • 简介：根据原数组长度n，创建n个桶，每个桶代表一个区间范围，区间跨度是(max - min) / (n-1)。遍历原数组，对应元素放到桶中，记录每个桶的最大最小值。遍历桶，统计每个桶的最大值和右侧非空桶的最小值的差，数值最大的差即为最大相邻差。

   • 代码：

     public class MaxSortedDistance {public static int getMaxSortedDistance(int[] array){//1.得到原数组的最大值和最小值 和 区间跨度int max = array[0];int min = array[0];for(int i=1; i<array.length; i++) {if(array[i] > max) {max = array[i];}if(array[i] < min) {min = array[i];}}int d = max - min;//如果max和min相等，说明数组所有元素都相等，返回0if(d == 0){return 0;}//2.初始化桶，桶的数量和元素的数量一样多int bucketNum = array.length;Bucket[] buckets = new Bucket[bucketNum];for(int i = 0; i < bucketNum; i++){buckets[i] = new Bucket();}//3.遍历原始数组，确定每个桶的最大最小值for(int i = 0; i < array.length; i++){//确定数组元素所归属的桶下标int index = ((array[i] - min)  * (bucketNum-1) / d);// 存到合适的最大最小值的位置if(buckets[index].min==null || buckets[index].min>array[i]){buckets[index].min = array[i];}if(buckets[index].max==null || buckets[index].max<array[i]){buckets[index].max = array[i];}}//4.遍历桶，找到最大差值int leftMax = buckets[0].max;  // 存储第一个桶的最大值int maxDistance = 0;for (int i=1; i<buckets.length; i++) {// 如果右侧的桶没有最小值，就直接遍历下一个桶if (buckets[i].min == null) {  continue;}// 记录好最大差if (buckets[i].min - leftMax > maxDistance) {maxDistance = buckets[i].min - leftMax;}leftMax = buckets[i].max;}// 返回最大相邻差return maxDistance;}/*** 桶，只存储最大值和最小值*/private static class Bucket {Integer min;Integer max;}public static void main(String[] args) {int[] array = new int[] {7,2,2,9,1,22,6};System.out.println(getMaxSortedDistance(array));}
     }

   • 时间复杂度和空间复杂度都是$O(n)$