算法leetcode

力扣164-最大间距

字数统计: 820字   |   阅读时长: 3分
,

摘要: 桶排序的经典问题。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 非比较排序 中，我们学习了计数排序、桶排序、基数排序的原理、代码模板、题目，本文我们看一个稍微难点的问题，但很经典，使用桶排序的思想解决。这种分桶的思想在很多问题中都有应用，参考文章 分桶法。

$1 题目

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

提示:

1
2
1 <= nums.length <= 1e5
0 <= nums[i] <= 1e9

示例 1:
输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

$2 题解

算法: 桶排序

初始数据的图像呈一条无规则的折线，排序后变成了一条单调不减的折线。

最大值为 MAX，最小值为 MIN。n 个元素，一共有 n - 1 个相邻的间隔。

如果这些间隔均相同，则间隔为 (MAX - MIN) / (n - 1) 即为答案。

如果这些不是全都相同，则最大间隔一定有大于 (MAX - MIN) / (n - 1) 的，即不会所有的间隔全都小于 (MAX - MIN) / (n - 1)，这个结论可以用组合数学中的鸽巢原理说明。

因此如果取间隔小于等于 (MAX - MIN) / (n - 1) 的桶，最大间隔一定不在同一个桶里。

1
2
3
4
5
step1: 取一个合适的桶宽 1 <= b <= (MAX - MIN) / (n - 1)
step2: 桶的个数为 nb = (MAX - MIN) / b + 1
step3: 第 j 个桶对应的区间 [MIN + (j - 1) * b, MIN + j * b)，j 从 1 开始
step4: 求 nums[i] 属于那个桶: (nums[i] - MIN) / b
step5: 比较 k 个有元素的桶

代码(c++)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return 0;
        int MAX = INT_MIN, MIN = INT_MAX;
        for(int num: nums)
        {
            MAX = max(MAX, num);
            MIN = min(MIN, num);
        }
        if(MAX - MIN == 0) return 0;
        int b = max(1, (MAX - MIN) / (n - 1)); // 桶宽下取整
        int nb = 1 + (MAX - MIN) / b; // 桶个数上取整
        vector<Bucket> buckets(nb, Bucket());
        // 第 i 个桶的取值范围 [MIN + i * b, MIN + (i + 1) * b)
        // i = 0 .. nb - 1 (共 nb 个桶)
        // 给定 val 的桶 id: bucket_id = (val - MIN) / b 下取整
        for(int num: nums)
        {
            int bucket_id = (num - MIN) / b;
            buckets[bucket_id].maxx = max(buckets[bucket_id].maxx, num);
            buckets[bucket_id].minx = min(buckets[bucket_id].minx, num);
            buckets[bucket_id].used = true;
        }
        int result = 0;
        int iter = 0;
        int prev_max = 0;
        while(iter < nb && !buckets[iter].used)
            ++iter;
        if(iter == nb) return result;
        prev_max = buckets[iter].maxx;
        while(iter < nb)
        {
            while(iter < nb && !buckets[iter].used)
                ++iter;
            if(iter == nb) break;
            result = max(result, buckets[iter].minx - prev_max);
            prev_max = buckets[iter].maxx;
            ++iter;
        }
        return result;
    }

private:
    struct Bucket {
        int maxx;
        int minx;
        bool used;
        Bucket():maxx(INT_MIN), minx(INT_MAX), used(false){}
    };
};
Share