【算法】【数组与矩阵模块】桶排序思想解决无序数组排序后相邻数间的最大差值

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个无序数组arr，求数组arr排好序之后，相邻数间的最大差值
如：
arr = [1,9,10]
结果为 9 - 1 = 8

解决方案

原问题：
1、首先创建一个桶数组，每一个桶只记录当前桶中的最大值和最小值，桶数组的长度为arr.len-1
2、获取整个数组中的最大值和最小值，将最大值放入bucket[arr.len]
3、计算桶的范围，(最大值-最小值)/桶数量-1
4、根据桶范围和每一个值，计算出来每一个值的桶编号，放入桶中
5、遍历桶，计算最长的空桶子数组，将该子数组的前后桶拿出来，后桶的最小值-前桶的最大值即可。

代码编写

java语言版本

原问题：
方法一:

    /*** 二轮测试：获取数组排序后相邻之间的最大值* @param arr* @return*/public static int getMaxSubCp1(int[] arr) {if (arr == null || arr.length == 0) {return -1;}if (arr.length == 1) {return 0;}// 桶个数int bNum = arr.length+1;// 桶列表,这里长度不会改变的使用数组类型Record[] records = new Record[bNum + 1];init(records);Record maxAndMin = getMaxAndMin(arr);int max = maxAndMin.getMaxValue();int min = maxAndMin.getMinValue();// 桶中的范围int dis = (int)Math.ceil((max - min + 1) / (bNum-1));// 最大值放入最后一个桶records[bNum].updateMaxOrMin(max);// 剩下的开始分类放入桶中for (int i = 0; i < arr.length; i++) {if (max == arr[i]) {continue;}// 桶号int bucketNum = (arr[i] - min) / dis;records[bucketNum].updateMaxOrMin(arr[i]);}// 找到桶中第一个不为空的indexint noEmpty = 0;while (records[noEmpty].isEmpty()) {noEmpty++;}// 记录上一个非空位置int lastNoEmpty = noEmpty;int res = 0;// 循环找到除当前位置外的非空桶while (noEmpty < records.length) {if (noEmpty != lastNoEmpty && !records[noEmpty].isEmpty()){// 找到一个res = Math.max(res, records[noEmpty].getMinValue() - records[lastNoEmpty].getMaxValue());lastNoEmpty = noEmpty;}noEmpty++;}return res;}/*** 初始化* @param records*/private static void init(Record[] records) {for (int i = 0; i < records.length; i++) {records[i] = new Record(Integer.MIN_VALUE, Integer.MAX_VALUE);}}/*** 获取arr中的最值* @param arr* @return*/private static Record getMaxAndMin(int[] arr) {int min = arr[0];int max = arr[0];for (int i = 0; i < arr.length; i++) {min = Math.min(arr[i], min);max = Math.max(arr[i], max);}return new Record(max, min);}/*** 每一个桶只记录最大值和最小值就行*/protected static class Record {private Integer maxValue;private Integer minValue;private LinkedList<Integer> bucket;public Record(Integer maxValue, Integer minValue) {this.maxValue = maxValue;this.minValue = minValue;}/*** 拓展构造函数* @param maxValue* @param minValue* @param bucket*/public Record(Integer maxValue, Integer minValue, LinkedList<Integer> bucket) {this.maxValue = maxValue;this.minValue = minValue;this.bucket = bucket;}public Integer getMaxValue() {return maxValue;}public void setMaxValue(Integer maxValue) {this.maxValue = maxValue;}public Integer getMinValue() {return minValue;}public void setMinValue(Integer minValue) {this.minValue = minValue;}/*** 判断当前值是否能够更新最值* @param value*/public void updateMaxOrMin(int value) {this.maxValue = Math.max(this.maxValue, value);this.minValue = Math.min(this.minValue, value);}/*** 当前桶是否为空* 最值没有更新过*/public boolean isEmpty() {return this.maxValue == Integer.MIN_VALUE && this.minValue == Integer.MAX_VALUE;}}public static void main(String[] args) {System.out.println(getMaxSubCp1(new int[]{1,3,9,10}));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这里有几个点需要注意一下：
1、桶的长度为arr.len+1，但是除了最大值外，其他的数都不能到最大的桶中，这个就是通过计算范围时，除数是桶数-1来控制的，并且向上取整来保证。
2、桶的个数比arr的长度多一个1，就表示一定会出现一个或者多个空桶，那么我就想假如是1~10，桶个数是11个，间隔是1，这样的话，出现空桶也只能计算出来最大长度是1，如果存在间隔为2的，一定会出现两个空桶。
3、第三个问题就是计算空桶最大长度的问题，刚开始我觉得要求连续的空桶长度，那么要两个游标，在计算完成后，一个游标要循环到下一个空桶段的起点，然后再开始继续判断，其实换一种思路来看，连续的桶也可以看成是空桶段，只不过空桶段中没有空桶而已，所以问题就变成了，如果当前index不是起点并且不是空桶，那么就计算长度，并将当前位置作为下一个的起点，整个思路的代码量就减少了很多。这个解释有点不太好理解，大家可以借鉴一下最后那个计算最长空桶段的代码。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给[e-mail]
再次感谢左大神对我算法的指点迷津！