桶排序思想及FindMaxGap问题

用户5513909

发布于 2023-04-25 11:29:12

1780

发布于 2023-04-25 11:29:12

文章被收录于专栏：小鱼儿我的学习笔记小鱼儿我的学习笔记

桶排序思想介绍：桶排序介绍相邻两数最大差值问题有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。

给定一个int数组A和A的大小n

思路：

定义一个长度为待排序数组arr,长度为length, 然后用一个length + 1的数组用来抽象的表示桶；
取出arr中的最小值和最大值，把min到max范围等分成length + 1份，根据((num - min) * len / (max - min))将每个元素分到length+1个桶中。其中必存在至少一个空桶。
因为空桶的存在，最大差值一定不来自同一个桶中。因为从1号桶开始（因为0号桶一定非空），如果是空的，跳到下一个桶，如果是非空的，找前一个非空桶。对于每一个非空桶，都找它前一个非空桶的max和当前这个桶的min，通过max-min计算差值，去其中最大的一个。

问题：最大差值一定来自空桶的左右两个桶吗？

如上图所示，显然不是。方法的空桶只是用来排除最大差值在同一桶中出现可能。

public class findMaxGap {
    public static int maxGap(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
       	//获得数组最大最小值
        int len = arr.length;
        int min = Integer.MIN_VALUE;
        int max = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        if(min == max) {
            return 0;
        }
		//将数组等分为length+1
		//每一个同桶中，只存储最大、最小值，和判断桶中是否有元素的bool变量
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        int bid = 0;
        for (int i = 0; i < len; i++) {
            bid = bucket(arr[i], len, min, max);
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], arr[i]) : arr[i];
            hasNum[bid] = true;
        }
        int res = 0;
        int lastMax = maxs[0];
        for (int i = 1; i <= len; i++){
            if (hasNum[i]){
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }
	//返回该元素所属的桶
    public static int bucket(long num, long len, long min, long max){
        return (int) ((num - min) * len / (max - min));
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-29，如有侵权请联系 cloudcommunity@tencent.com 删除

int