Leetcode No.164 最大间距(桶排序)
2023-04-18 16:59:09 时间
一、题目描述
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。 如果数组元素个数小于 2,则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。
说明: 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
二、解题思路
桶排序的两个核心问题:
1、每个桶的长度是多少?换句话说,每个桶放置元素的范围是什么? 2、一共要准备多少个桶?
分析和解答: 1、我们期望将数组中的各个数等距离分配,也就是每个桶的长度相同,也就是对于所有桶来说,桶内最大值减去桶内最小值都是一样的。可以当成公式来记。
2、确定桶的数量,最后的加一保证了数组的最大值也能分到一个桶。
3、我们的做法是要将数组中的数放到一个个桶里面,不断更新更大的(后一个桶内元素的最小值 - 前一个桶内元素的最大值),最后就得到了答案。 4、如何确定每个数应该对应哪个桶?
三、代码
public class Solution2 {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
// 找出最大值和最小值 为了方便后面确定桶的数量
int minVal = Arrays.stream(nums).min().getAsInt();
int maxVal = Arrays.stream(nums).max().getAsInt();
// 确定桶的间距
int d = Math.max(1, (maxVal - minVal) / (n - 1));
// 确定桶的个数
int bucketSize = (maxVal - minVal) / d + 1;
int[][] bucket = new int[bucketSize][2];
for (int i = 0; i < bucketSize; ++i) {
// 存储 (桶内最小值,桶内最大值) 对, (-1, -1) 表示该桶是空的
Arrays.fill(bucket[i], -1);
}
for (int i = 0; i < n; i++) {
//找到每一个值所对应桶的索引
int idx = (nums[i] - minVal) / d;
//该桶是空的
if (bucket[idx][0] == -1) {
//最大值和最小值都设置为nums[i]
bucket[idx][0] = bucket[idx][1] = nums[i];
} else {
// 更新每个桶的数据
bucket[idx][0] = Math.min(bucket[idx][0], nums[i]);
bucket[idx][1] = Math.max(bucket[idx][1], nums[i]);
}
}
//ret表示桶之间最大的差距
int ret = 0;
//preMax 表示前一个桶的最大值
int prev = -1;
for (int i = 0; i < bucketSize; i++) {
//表示某一个桶为空
if (bucket[i][0] == -1) {
continue;
}
//但凡某一个桶不为空,都会在前面的数据中更新掉bucketMax的值
if (prev != -1) {
//用后一个桶的最小值减前一个桶的最大值,可以得到最大间距。
ret = Math.max(ret, bucket[i][0] - bucket[prev][1]);
}
prev = i;
}
return ret;
}
}
四、复杂度分析
时间复杂度:O(N),其中 N 是数组的长度。注意到桶的数量为(max−min)/d≈N−1=O(N)。
空间复杂度:O(N),其中 N 是数组的长度。我们开辟的空间大小取决于桶的数量。
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击