最大间隔数-桶排序应用

public class MaximumGap {

    public static int maximumGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int len = arr.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_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;
        }
        boolean book[] = new boolean[len + 1];
        int maxs[] = new int[len + 1];
        int mins[] = new int[len + 1];
        int id = 0;
        for (int i = 0; i < len; i++) {
            // 划分桶号
            id = (int) ((arr[i] - min) * len / (max - min));
            mins[id] = book[id] ? Math.min(mins[id], arr[i]) : arr[i];
            maxs[id] = book[id] ? Math.max(maxs[id], arr[i]) : arr[i];
            book[id] = true;
        }
        int res = 0;
        // 第一个桶内默认是最小值
        int lastMax = maxs[0];
        int i = 1;
        for (; i <= len; i++) {
            if (book[i]) {
                // 两个相邻的非空桶，后一个的最小值减去前一个的最大值为相对间隔最大值
                res = Math.max(res, mins[i] - lastMax);
                // 当前桶的最大值更新为前一个最大值
                lastMax = maxs[i];
            }
        }
        return res;

    }

    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        Arrays.sort(arr);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++) {
            gap = Math.max(arr[i] - arr[i - 1], gap);
        }
        return gap;
    }

    public static int[] getRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // 获取 -maxVlaue + 1 ~ maxValue 的值
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }

        return arr;

    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] book = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            book[i] = arr[i];
        }
        return book;
    }

    public static void main(String[] args) {
        // 测试次数
        int test = 50000;

        // 数组长度
        int maxSize = 100;

        // 最大数值
        int maxValue = 100;

        boolean flag = true;

        for (int i = 0; i < test; i++) {
            int arr1[] = getRandomArray(maxSize, maxValue);
            // 拷贝比较
            int arr2[] = copyArray(arr1);
            if (maximumGap(arr1) != comparator(arr2)) {
                flag = false;
                break;
            }

        }
        System.out.println(flag ? "测试正常" : "发生错误");
        // 随机测试一组数据
        int arr[] = getRandomArray(maxSize, maxValue);
        int t = maximumGap(arr);
        System.out.println("原数组:"+Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
        System.out.println("最大差值:"+t);
    }
}