力扣164-最大间距

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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