[LeetCode] 164. 最大间距
2024-09-05 19:10:01
题目链接 : https://leetcode-cn.com/problems/maximum-gap/
题目描述:
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。
如果数组元素个数小于 2,则返回 0。
示例:
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。
说明:
- 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。
- 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
思路:
不用线性时间复杂度,其实就是排序的题!代码如下:
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2: return 0
res = 0
nums.sort()
for i in range(1, n):
res = max(res, nums[i] - nums[i - 1])
return res
下面介绍一下用桶排序的方法:
首先,要知道很关键一点:相邻的最大差值一定不小于该数组的最大值减去最小值除以间隔个数,取上界。即 $ \lceil \frac{max_num - min_num }{ (n - 1)} \rceil $ ,这里的 n
是数组的个数。
我们可以用反证法证明,如果小于,会怎么呢?比如 [1, 2, 5]
, 利用上式得 \(gap = \frac {5 - 1}{2} = 2\)。如果假设相邻间隔最大为 1
,那必然不能组成以上数组!
接下来,我们开始放桶,一个桶里放多少个数呢?我们可以把相邻间隔小于 gap
放在一个桶里,那么最大间隔一定在相互桶之间产生!
如何判断这个数在哪个桶里呢?我们用 $ \lfloor { \frac{num - min_num}{gap}}\rfloor$表示 num
在哪个桶里(换句话说,离min_num
有几个gap
)。我们比如数组为 [1, 2, 3, 4,7]
,我们排除最大值和最小值, 把其他数组放入桶中,如下图:
| | | |
|2,3 | | 4 |
|_ _ _| | _ _ _|
同一个桶里,绝对不会出现最大的相邻的差值!
所以,我们只需要比较桶之间的差值,这样我们只需要保持同一桶里的最大值,和最小值即可!
代码如下:
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2: return 0
max_num = max(nums)
min_num = min(nums)
gap = math.ceil((max_num - min_num)/(n - 1))
bucket = [[float("inf"), float("-inf")] for _ in range(n - 1)]
#print(bucket)
# 求出每个桶的最大值,和最小值
for num in nums:
if num == max_num or num == min_num:
continue
loc = (num - min_num) // gap
bucket[loc][0] = min(num, bucket[loc][0])
bucket[loc][1] = max(num, bucket[loc][1])
##print(bucket)
# 遍历整个桶
preMin = min_num
res = float("-inf")
for x, y in bucket:
if x == float("inf") :
continue
res = max(res, x - preMin)
preMin = y
res = max(res, max_num - preMin)
return res
最新文章
- 使用jQuery封装实用函数
- python面向对象中的__init__方法怎么理解?
- LCA算法的理解
- 你还记的那一年你我学习的-->;>;用表组织数据*(数据表)
- EF 4.1 一些操作
- C#操作Excel,对Sheet插入次序的控制 (有待完善)
- 比較Backbone.js, Angular.js, Ember.js, Knockout.js 心得
- MSDN 2005 安装问题
- iOS 获取手机的型号,系统版本,软件名称,软件版本
- B - Networking - poj 1287
- xdu_RainAndBow 鞍山打铁记
- android 设置头像以及裁剪功能
- 14-TypeScript简单工厂模式
- Python网络爬虫精要
- AsyncTask 进行耗时操作和UI 更新
- NumPy学习_01 ndarray相关概念
- windows程序设计 MessageBox消息框
- 面试加分项---HashMap底层实现原理
- host文件的用处
- 【Spark】Spark Streaming 动态更新filter关注的内容
热门文章
- spring boot2.0.2,<;-1.4.8
- 使用 CSS 显示 XML
- BZOJ 3545: [ONTAK2010]Peaks 启发式合并 + 离线 + Splay
- Quartz监听器
- spring 接口校验参数(自定义注解)
- [CSP-S模拟测试]:异或(数学)
- 在ThinkPHP框架(5.0.24)下引入Ueditor并实现向七牛云对象存储上传图片同时将图片信息保存到MySQL数据库,同时实现lazyload懒加载
- 解析JSON有俩种方式:JSONObject和GSON
- PTA编程总结一
- FineReport打印方式(转)