题目描述(困难难度)

给一个乱序的数组,求出数组排序以后的相邻数字的差最大是多少。

解法一

先来个直接的,就按题目的意思,先排序,再搜索。

public int maximumGap(int[] nums) {
    Arrays.sort(nums);
    int max = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i + 1] - nums[i] > max) {
            max = nums[i + 1] - nums[i];
        }
    }
    return max;
}

但是正常的排序算法时间复杂度会是 O(nlog(n)),题目要求我们在 O(n) 的复杂度下去求解。

自己想了各种思路,但想不出怎么降到 O(n),把 官方 给的题解分享一下吧。

我们一般排序算法多用快速排序,平均时间复杂度是 O(nlog(n)),其实还有一种排序算法,时间复杂度是 O(kn)k 是最大数字的位数,当 k 远小于 n 的时候,时间复杂度可以近似看成 O(n)。这种排序算法就是基数排序,下边讲一下具体思想。

比如这样一个数列排序: 342 58 576 356, 我们来看一下怎么排序:

不足的位数看做是 0
342 058 576 356
按照个位将数字依次放到不同的位置
0: 
1: 
2: 342
3: 
4: 
5: 
6: 576, 356
7: 
8: 058
9: 

把上边的数字依次拿出来,组成新的序列 342 576 356 058,然后按十位继续放到不同的位置。
0: 
1: 
2: 
3: 
4: 342
5: 356 058
6: 
7: 576
8: 
9: 

把上边的数字依次拿出来,组成新的序列 342 356 058 576,然后按百位继续装到不同的位置。
0: 058
1: 
2: 
3: 342 356
4: 
5: 576 
6: 
7: 
8: 
9: 

把数字依次拿出来,最终结果就是 58 342 356 576

为了代码更好理解, 我们可以直接用 10list 去存放每一组的数字,官方题解是直接用一维数组实现的。

对于取各个位的的数字,我们通过对数字除以 1, 10, 100... 然后再对 10 取余来实现。

public int maximumGap(int[] nums) {
    if (nums.length <= 1) {
        return 0;
    }
    List<ArrayList<Integer>> lists = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        lists.add(new ArrayList<>());
    }
    int n = nums.length;
    int max = nums[0];
    //找出最大的数字
    for (int i = 1; i < n; i++) {
        if (max < nums[i]) {
            max = nums[i];
        }
    }
    int m = max;
    int exp = 1;
    //一位一位的进行
    while (max > 0) {
        //将之前的元素清空
        for (int i = 0; i < 10; i++) {
            lists.set(i, new ArrayList<>());
        }
        //将数字放入对应的位置
        for (int i = 0; i < n; i++) {
            lists.get(nums[i] / exp % 10).add(nums[i]);
        }

        //将数字依次拿出来
        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < lists.get(i).size(); j++) {
                nums[index] = lists.get(i).get(j);
                index++;
            }

        }
        max /= 10;
        exp *= 10;
    }

    int maxGap = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i + 1] - nums[i] > maxGap) {
            maxGap = nums[i + 1] - nums[i];
        }
    }
    return maxGap;
}

解法二

上边的解法还不是真正的 O(n),下边继续介绍另一种解法,参考了 这里-time-and-space) ,评论区对自己帮助很多。

我们知道如果是有序数组的话,我们就可以通过计算两两数字之间差即可解决问题。

那么如果是更宏观上的有序呢?

我们把 0 3 4 6 23 28 29 33 38 依次装到三个箱子中
    0            1            2           3
 -------      -------      -------     ------- 
|  3 4  |    |       |    | 29    |   | 33    |
|   6   |    |       |    |  23   |   |       |
|  0    |    |       |    |  28   |   |  38   |
 -------      -------      -------     ------- 
  0 - 9       10 - 19      20 - 29     30 - 39
我们把每个箱子的最大值和最小值表示出来
 min  max     min  max     min  max  min  max 
 0     6      -     -      23   29   33   38

我们可以只计算相邻箱子 minmax 的差值来解决问题吗?空箱子直接跳过。

2 个箱子的 min 减第 0 个箱子的 max23 - 6 = 17

3 个箱子的 min 减第 2 个箱子的 max33 - 29 = 4

看起来没什么问题,但这样做一定需要一个前提,因为我们只计算了相邻箱子的差值,没有计算箱子内数字的情况,所以我们需要保证每个箱子里边的数字一定不会产生最大 gap

我们把箱子能放的的数字个数记为 interval,给定的数字中最小的是 min,最大的是 max。那么箱子划分的范围就是 min ~ (min + 1 * interval - 1)(min + 1 * interval) ~ (min + 2 * interval - 1)(min + 2 * interval) ~ (min + 3 * interval - 1)...,上边举的例子中, interval 我们其实取了 10

划定了箱子范围后,我们其实很容易把数字放到箱子中,通过 (nums[i] - min) / interval 即可得到当前数字应该放到的箱子编号。那么最主要的问题其实就是怎么去确定 interval

interval 过小的话,需要更多的箱子去存储,很费空间,此外箱子增多了,比较的次数也会增多,不划算。

interval 过大的话,箱子内部的数字可能产生题目要求的最大 gap,所以肯定不行。

所以我们要找到那个保证箱子内部的数字不会产生最大 gap,并且尽量大的 interval

继续看上边的例子,0 3 4 6 23 28 29 33 38,数组中的最小值 0 和最大值 38 ,并没有参与到 interval 的计算中,所以它俩可以不放到箱子中,还剩下 n - 2 个数字。

像上边的例子,如果我们保证至少有一个空箱子,那么我们就可以断言,箱子内部一定不会产生最大 gap

因为在我们的某次计算中,会跳过一个空箱子,那么得到的 gap 一定会大于 interval,而箱子中的数字最大的 gapinterval - 1

接下来的问题,怎么保证至少有一个空箱子呢?

鸽巢原理的变形,有 n - 2 个数字,如果箱子数多于 n - 2 ,那么一定会出现空箱子。总范围是 max - min,那么 interval = (max - min) / 箱子数,为了使得 interval 尽量大,箱子数取最小即可,也就是 n - 1

所以 interval = (max - min) / n - 1 。这里如果除不尽的话,我们 interval 可以向上取整。因为我们给定的数字都是整数,这里向上取整的话对于最大 gap 是没有影响的。比如原来范围是 [0,5.5),那么内部产生的最大 gap5 - 0 = 5。现在向上取整,范围变成[0,6),但是内部产生的最大 gap 依旧是 5 - 0 = 5

所有问题都解决了,可以安心写代码了。

public int maximumGap(int[] nums) {
    if (nums.length <= 1) {
        return 0;
    }
    int n = nums.length;
    int min = nums[0];
    int max = nums[0];
    //找出最大值、最小值
    for (int i = 1; i < n; i++) {
        min = Math.min(nums[i], min);
        max = Math.max(nums[i], max);
    }
    if(max - min == 0) {
        return 0;
    }

    //算出每个箱子的范围
    int interval = (int) Math.ceil((double)(max - min) / (n - 1));

    //每个箱子里数字的最小值和最大值
    int[] bucketMin = new int[n - 1];
    int[] bucketMax = new int[n - 1];

    //最小值初始为 Integer.MAX_VALUE
    Arrays.fill(bucketMin, Integer.MAX_VALUE);
    //最小值初始化为 -1,因为题目告诉我们所有数字是非负数
    Arrays.fill(bucketMax, -1);

    //考虑每个数字
    for (int i = 0; i < nums.length; i++) {
        //当前数字所在箱子编号
        int index = (nums[i] - min) / interval;
        //最大数和最小数不需要考虑
        if(nums[i] == min || nums[i] == max) {
            continue;
        }
        //更新当前数字所在箱子的最小值和最大值
        bucketMin[index] = Math.min(nums[i], bucketMin[index]);
        bucketMax[index] = Math.max(nums[i], bucketMax[index]);
    }

    int maxGap = 0;
    //min 看做第 -1 个箱子的最大值
    int previousMax = min;
    //从第 0 个箱子开始计算
    for (int i = 0; i < n - 1; i++) {
        //最大值是 -1 说明箱子中没有数字,直接跳过
        if (bucketMax[i] == -1) {
            continue;
        }

        //当前箱子的最小值减去前一个箱子的最大值
        maxGap = Math.max(bucketMin[i] - previousMax, maxGap);
        previousMax = bucketMax[i];
    }
    //最大值可能处于边界,不在箱子中,需要单独考虑
    maxGap = Math.max(max - previousMax, maxGap);
    return maxGap;

}

这道题主要是对排序算法的了解,第一次见到了基数排序的应用,解法三其实是桶排序的步骤。

results matching ""

    No results matching ""