桶排序思想及FindMaxGap问题

2023-04-25 11:29:12 浏览数 (2)

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

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

思路:

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

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

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

代码语言:javascript复制
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));
    }
}

0 人点赞