最大间距

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

LeetCode每日一题，164. Maximum Gap

先看题目描述

DwKCgs.png

大意就是给定一个未排序的数组，让我们返回排序后数组中相邻元素的最大差值

算法和思路

排序后遍历

大致思路就是先对原数组排序，使其按照升序排列，然后遍历排序后数组，遍历过程中用一个变量 max 维护相邻元素的差值的最大值，最后返回 max 即可

算法源码

自己一开始实现的代码，为了偷懒就直接调用了 Java 内部的 Arrays.sort() 排序函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Arrays;

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

后来去看题解，因为题目要求时间复杂度达到 O(n)，所以不能用传统的基于比较的排序算法，例如基数排序就可以在 O(n) 的时间内完成整数的排序，自己之前一直对基数排序不太了解，只知道大致原理，但不清楚具体代码该怎么实现，看了题解的代码才对基数排序的具体代码实现有了一定了解，但虽然是说时间复杂度能达到 O(n)，但实际运行起来并没有 Java 内部的排序方法速度快，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Arrays;

class Solution {
    public int maximumGap(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return 0;
        }
        int max = 0;
        int maxVal = Arrays.stream(nums).max().getAsInt();
        long exp = 1;
        int[] buf = new int[len];

        while (maxVal >= exp) {
            int[] cnt = new int[10];
            for (int num : nums) {
                int digit = (num / (int)exp) % 10;
                cnt[digit]++;
            }
            for (int i = 1; i < 10; i++) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = len - 1; i >= 0; i--) {
                int digit = (nums[i] / (int)exp) % 10;
                buf[cnt[digit] - 1] = nums[i];
                cnt[digit]--;
            }
            System.arraycopy(buf, 0, nums, 0, len);
            exp *= 10;
        }

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