当前位置：首页 > article >正文

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

article 2025/1/14 0:18:28

前言

当前所有算法都使用测试用例运行过，但是不保证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]);
        }
        // 找到桶中第一个不为空的index
        int 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不是起点并且不是空桶，那么就计算长度，并将当前位置作为下一个的起点，整个思路的代码量就减少了很多。这个解释有点不太好理解，大家可以借鉴一下最后那个计算最长空桶段的代码。