0164. Maximum Gap - kumaeki/LeetCode GitHub Wiki

0164. Maximum Gap

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Example 1:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^9

解法1

其实这个方法是不满足题目的.因为时间复杂度不是N而是NlogN.

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

解法2

基数排序 (Radix Sort) 。

假设有 4个数字 342 58 576 356, k(进制)为10, d(最大位数)为3,排序过程如下

input：

342 58 576 356

第一次排序

公式 ： (nums[i] /1) % 10), 取得的个位数的值分别为

342->2
 58->8
576->6
356->6

按值排序

0 : 
1 : 
2 : 342 
3 : 
4 :
5 :
6 : 576 , 356  
7 : 
8 : 58 
9 :

得到： 342 , 576 , 356 , 58

第二次排序

公式 ： (nums[i] /10) % 10), 取得的十位数的值分别为

342->4
576->7
356->5
 58->5

按值排序

0 : 
1 : 
2 : 
3 : 
4 : 342 
5 : 356 , 58 
6 : 
7 : 576 
8 : 
9 :

得到 ： 342 , 356 , 58 , 576

第三次排序

公式 ： (nums[i] /100) % 10), 取得的百位数的分别值为

342->3
356->3
 58->0
576->5

按值排序

 0 : 58 
 1 : 
 2 : 
 3 : 342 , 356 
 4 : 
 5 : 576 
 6 : 
 7 : 
 8 : 
 9 :

得到 ： 58 , 342 , 356 , 576 (最终结果)

class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2)
            return 0;
        int max = nums[0], n = nums.length;
        // 取得最大值
        for (int i = 1; i < n; i++)
            if (nums[i] > max)
                max = nums[i];

        int exp = 1, radix = 10;
        // 二维列表, 计数排序用
        List<List<Integer>> list = new ArrayList<List<Integer>>(10);
        for (int i = 0; i < 10; i++)
            list.add(new ArrayList<Integer>());

        while (max > 0) {
            // 开始排序前清空
            for (int i = 0; i < 10; i++)
                list.set(i, new ArrayList<Integer>());

            // 将前一次计数排序完成的数组,依次进行当前位数的排序
            // 第一次排序(针对个位数进行排序)时,是原始的输入数组
            // 待排序数字在当前位数的值 ＝ nums[i] / exp % radix
            for (int i = 0; i < n; i++)
                list.get(nums[i] / exp % radix).add(nums[i]);

            int index = 0;
            // 从小到大,将数字重新放回nums中
            for (List<Integer> l : list) {
                for (int num : l) {
                    nums[index++] = num;
                }
            }
            // 进行下一个位数的排序
            max /= radix;
            exp *= radix;
        }

        int res = 0;
            for (int i = 1; i < n; i++)
            res = Math.max(res, nums[i] - nums[i - 1]);
        return res;
    }
}

解法3

不用二维数组, 而是用一维数组解决这个问题.

input：

342 58 576 356

第一次排序

公式 ： (nums[i] /1) % 10), 取得的个位数的值分别为 (从0开始计数)

342->2
 58->8
576->6
356->6

计数结果为(从1开始计数, 和上一个取值步骤从0开始计数有一位的差值,这导致后面计算新的位置的时候要减去1)

0 : 
1 : 
2 : 1
3 : 
4 : 
5 : 
6 : 2
7 : 
8 : 1
9 :

累进相加之后得到

0 : 
1 : 
2 : 1
3 : 
4 : 
5 : 
6 : 3 (1 + 2)
7 : 
8 : 4 (3 + 1)
9 :

对于前一次排序的结果(初始状态),倒序计算出新的位置

前一次排序结果(初始状态) 342 58 576 356<br>
356 -> 个位数为6 -> 对应的值为3 (递减1)-> 新的位置为2
576 -> 个位数为6 -> 对应的值为2 (递减1)-> 新的位置为1
 58 -> 个位数为8 -> 对应的值为4 (递减1)-> 新的位置为3  
342 -> 个位数为2 -> 对应的值为1 (递减1)-> 新的位置为0

得到 342 , 576 , 356 , 58

第二次排序

公式 ： (nums[i] /10) % 10), 取得的十位数的值分别为 (从0开始计数)

342->4
576->7
356->5 
 58->5

计数并累计相加后得到

0 : 
1 : 
2 : 
3 : 
4 : 1 -> 1
5 : 2 -> 3 (2 + 1)
6 : 
7 : 1 -> 4 (1 + 3)
8 : 
9 :

对于前一次排序的结果,倒序计算出新的位置

前一次排序结果 342 576 356 58
 58 -> 十位数为5 -> 对应的值为3 (递减1)-> 新的位置为2
356 -> 十位数为5 -> 对应的值为2 (递减1)-> 新的位置为1
576 -> 十位数为7 -> 对应的值为4 (递减1)-> 新的位置为3  
342 -> 十位数为4 -> 对应的值为1 (递减1)-> 新的位置为0

得到 342 , 356 , 58 , 576

第三次排序

公式 ： (nums[i] /100) % 10), 取得的百位数的值分别为 (从0开始计数)

342->3
356->3 
 58->0
576->5

计数并累计相加后得到

0 : 1 -> 1
1 : 
2 : 
3 : 2 -> 3 (2 + 1)
4 : 
5 : 1 -> 4 (1 + 3)
6 : 
7 : 
8 : 
9 :

对于前一次排序的结果,倒序计算出新的位置

前一次排序结果() 342 356 58 576
576 -> 百位数为5 -> 对应的值为4 (递减1)-> 新的位置为3  
 58 -> 百位数为0 -> 对应的值为1 (递减1)-> 新的位置为0
356 -> 百位数为3 -> 对应的值为2 (递减1)-> 新的位置为2
342 -> 百位数为3 -> 对应的值为2 (递减1)-> 新的位置为1

得到 最终结果58 , 342 , 356 , 576.

class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2)
            return 0;
        int max = nums[0], n = nums.length;
        // 取得最大值
        for (int i = 1; i < n; i++)
            if (nums[i] > max)
                max = nums[i];

        int exp = 1, radix = 10;
        // 和输入数组同样大小的备份数组
        int[] storage = new int[n];
        while (max > 0) {
            // 记录当前位数的值的个数
            int[] counts = new int[10];

            // 待排序数字在当前位数的值 ＝ nums[i] / exp % radix
            for (int i = 0; i < n; i++)
                counts[nums[i] / exp % radix]++;
            for (int i = 1; i < 10; i++)
                counts[i] += counts[i - 1];
            for (int i = n - 1; i >= 0; i--) {
                int index = --counts[nums[i] / exp % radix];
                storage[index] = nums[i];
            }
            for (int i = 0; i < n; i++)
                nums[i] = storage[i];
            max /= radix;
            exp *= radix;
        }

        int res = 0;
        for (int i = 1; i < n; i++)
            res = Math.max(res, nums[i] - nums[i - 1]);
        return res;
    }
}

解法4

对一个数组进行排序是非常费时的.在最差情况下,需要把每一个元素都和其他元素进行比较.但是,如果我们不进行所有元素的两两比较呢?如果我们能把他们分组 (或者说 桶,抽屉), 我们只需要比较这些桶就可以了.
假设数组中有n个元素. 如果有n个桶,那么可以做到每个桶中是一个元素.

那么,如果我们减少桶的数量会发生什么呢?就是至少有一个桶里面会有一个以上的元素.

抽屉原理

如果n＋１个元素放到n个集合中,那么至少有一个集合中有至少两个元素.

现在来分析一下数字间的差值.
首先是最理想的情况,已排序数组,并且相互之间的差值是相等的.那么对于 n 个元素,存在 n-1 个差值,我们设为 t ,那么有

t  = ( max - min ) / ( n - 1 )

实际上,在一个数组的最大值 max , 最小值 min 固定, 数组个数 n 固定的情况下, 上述 t 是答案的最小值(我们要求的是最大相邻间隔).
如果我们将 nums[i] - nums[i - 1] 的间隔减小为 t - p, 那么 nums[i + 1] - nums[i] 会增加到 t + p . 那么最终的结果就从 t 变为了 t - p

举例
[ 2 , 4 , 6 , 8 , 10]     n  =  5, min  = 2, max = 10 , t = ( 10 - 2) / 4 = 2, 最大间隔为2
[ 2 , 3,  6 , 8 , 10]     虽然2 到 3的间隔减小为1 但是3和6的间隔增大为3 , 所以最大间隔为3

回到我们的问题.
我们现在利用抽屉原理,把元素之间的比较变成了集合(桶)之间的比较.
这样可以减少比较的次数.但是这并没有解决问题.如果最大相邻间隔是在集合内部怎么办?
所以现在的问题就是,我们怎么来分组(把元素放入集合)才能保证集合之间的差值一定大于集合内元素的差值.
如果解决了这个问题,那么就可以用下面的步骤来得到答案：

将元素分组, 比较各个组之间的差值(前一个组的最大值和后一个组的最小值的差值), 得到最大值. 
组内各个元素之间不用排序,节省了大量的时间.

如何确定集合的宽度

假定给定数组[ 0, 1, 4, 11, 13, 15, 32, 35,37] 有集合宽度 = w , 第i个集合为[min + i * w , min + (i + 1) * w - 1],集合内的最大差值为 w - 1. 设 w = 10

[  0 ,  9 ]   0 ,  1 ,  4
[ 10 , 19 ]  11 , 13 , 15
[ 20 , 29 ]
[ 30 , 39 ]  32 , 35 , 37

设 w = 5

[ 0, 4]  0,  1, 4
[ 5, 9]
[10,14] 11, 13
[15,19] 15
[20,24]
[25,29]
[30,35] 32
[35,49] 35, 37

如果存在一个空集合,那么空集合前后的非空集合的差值就一定大于集合内最大差值 w-1. 但是w又不能太大,会影响性能.

那么应该怎么计算w, 使得存在一个空集合,同时w尽可能的小呢?

其实在分组的时候,第一个集合的最小值和最后一个集合的最大值是固定的, min 和max, 也就是说真正需要去执行分组操作的是除去max 和min 之外的n-2 个元素.

问题变成了 对于n-2个元素来说, 需要多少个集合才能保证至少一个集合是空的呢?

n-1个集合.

在n-1个集合的时候,集合宽度 w = (max - min) / ( n - 1), 也就是上面说的t, 相邻差值的最小值.

class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2)
            return 0;
        if (nums.length == 2)
            return Math.abs(nums[0] - nums[1]);

        int max = nums[0], min = nums[0], n = nums.length;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        if(max == min)
            return 0;
        int[] bucketMin = new int[n - 1], bucketMax = new int[n - 1];
        Arrays.fill(bucketMin, max);
        Arrays.fill(bucketMax, min);
        int w = (max - min) / (n - 1) + 1;
        for(int num : nums) {
            int index = (num - min) / w;
            bucketMin[index] = Math.min(bucketMin[index], num);
            bucketMax[index] = Math.max(bucketMax[index], num);
        }

        int res = 0, preMax = min;
        for (int i = 0; i < n - 1; i++) {
            if(bucketMax[i] == min)
                continue;
            res = Math.max(res, bucketMin[i] - preMax);
            preMax = bucketMax[i];
        }

        return res;
    }
}
⚠️ **GitHub.com Fallback** ⚠️