本文共 1588 字，大约阅读时间需要 5 分钟。

/** * 无序数组排序后的最大相邻差 * 思路： * 1、利用桶排序的思想，根据原数组的长度n，创建出n个桶，每个桶代表一个区间范围。其中第一个桶从原始数组的最小值minx开始，区间跨度是(max-min)/(n-1) * 2、遍历原数组，将原始数组每个元素插入到对应桶中，记录每个桶的最大和最小值 * 3、遍历所有桶，统计出每个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后相邻的最大值 * * 不需要像标准桶排序一样给没个桶内进行排序，只需要记录桶内最大值和最小值即可，时间复杂度稳定为O(n) */public class MaxSortedDistance {    public static int getMaxSortedDistance(int[] array){        //1、得到数列的最大值和最小值和差值d        int max = array[0];        int min = array[0];        for(int i=1;i
   
     max){                max = array[i];            }            if(array[i] < min){                min = array[i];            }        }        int d = max - min;        //如果max和min相等，说明数组中所有的值都相等        if(d == 0){            return 0;        }        //2、初始化桶        int bucketLength = array.length;        Bucket[] buckets = new Bucket[bucketLength];        for(int i =0;i
    
      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
     
       maxDistance){                maxDistance = buckets[i].min - leftMax;            }            leftMax = buckets[i].max;        }        return maxDistance;    }    private static class Bucket{        private Integer min;        private Integer max;    }    public static void main(String[] args) {        int[] array = new int[]{2,6,3,4,5,10,9};        System.out.println(getMaxSortedDistance(array));    }}
     
    
   

转载地址：http://xqsvi.baihongyu.com/