（Java热门面试热门题）Maxinum Gap问题

Z时代
2024-01-10
分类：综合

java

题目：

要求你设计一个时间复杂度为O(n)的算法，实现将一个无序数组排列好，然后求彼此之间的最大差值，而且不能使用非基于比较的排序算法。

分析

很明显这道题是故意坑人的，时间复杂度为O（n），那可不就是桶排序，基数排序和基数排序么，可是这些都是非基于比较的排序算法。所以不能直接用桶排序进行排序，我们需要用到这个算法的一个重要的思想，就是桶，比如给9个数字（数字的范围是从0到10），则准备10个（n个数字+1）桶装他们，比如：

每个桶都有三个参数：

1）是否有值

2）最大值

3）最小值

为什么会有最大值和最小值呢？如果十个数字，数字的范围是0-100呢？所以每个桶需要装的数字的范围是十个，如果出来一个11，一个12，则根据计算他们都应该在第1个桶内，所以需要把当前桶中的最大值和最小值求出来，什么时候相邻的两个数差值最大呢？

一定是后一个非空桶的最小值减去上一个非空桶的最大值的差值，什么意思呢？比如数组排好序以后是这样：

则需要5个桶，5,6在同一个桶中，5是桶里的最小值，6最桶中的最大值，10是5,6那个桶之后两个的桶中，他既是最大值也是最小值，故拿10-6得到的4作为结果，所以相邻元素最大差值是后一个非空桶的最小值减去上一个非空桶的最大值的差值。

上代码

package com.bean;
import java.util.Arrays;
public class MaxGap {
    public static int MaxGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        //求数组中最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //如果数组中最大值和最小值一样说明所有数字相同
        if (max == min) {
            return 0;
        }
        //最大值和最小值不同
        //需要比数组多一个桶，数组最小值最大值各占两个桶
        //其余数字被均匀分布在剩下的桶中
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        //bid是哪个桶的序号
        //把每个桶中的最大值和最小值求出来
        for (int i = 0; i < len; i++) {
            int bid = whichBucket(arr[i], len, max, min);
            maxs[bid] = hasNum[bid] ? Math.max(arr[i], maxs[bid]) : arr[i];
            mins[bid] = hasNum[bid] ? Math.min(arr[i], mins[bid]) : arr[i];
            hasNum[bid] = true;
        }
        //最后返回的那个最大值
        int res = 0;
        //前一个桶中最大的值
        int lastMax = maxs[0];
        int i = 1;
        for (; i <= len; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                //维护一下lastMax
                lastMax = maxs[i];
            }
        }
        return res;
    }
    //求当前数字属于哪个桶
    private static int whichBucket(int num, int length, int max, int min) {
        return (int) ((num - min) * length / (max - min));
    }
    //时间复杂度较高但是绝对正确的比较器
    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        //先排序,然后依次比较大小
        Arrays.sort(arr);
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++) {
            res = Math.max(res, arr[i] - arr[i - 1]);
        }
        return res;
    }
    //生成随机数组
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            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[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (MaxGap(arr1) != comparator(arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Congraduation!" : "Oops!Smfh!");
    }
}