【面试经典150 | 区间】用最少数量的箭引爆气球-CSDN博客
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
文章目录
Tag
【合并区间】【排序】【数组】
题目来源
题目解读
每个气球都有一个占据x轴的一个范围在这个范围里射出一只箭就会引爆该气球现在有一堆排布好的气球试问引爆所有的气球至少需要多少支箭。
解题思路
方法一合并区间
气球都是以区间的形式给出的那么我们将有交集的区间进行合并然后剩下的区间每个区间都需要一只箭来引爆q
实现代码
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int res = 1;
sort(points.begin(), points.end());
int r = points[0][1];
for (int i = 1; i < points.size(); ++i) {
if (points[i][0] > r) {
++res;
}
else {
points[i][0] = max(points[i-1][0], points[i][0]);
points[i][1] = min(points[i-1][1], points[i][1]);
}
r = points[i][1];
}
return res;
}
};
复杂度分析
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
n
n
n 为数组 points
的长度。
空间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)额外的空间是排序占据的空间。
其他语言
python3
合并区间
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort()
r = points[0][1]
n = len(points)
res = 1
for i in range(1, n):
if points[i][0] > r:
res += 1
else:
points[i][0] = max(points[i-1][0], points[i][0])
points[i][1] = min(points[i-1][1], points[i][1])
r = points[i][1]
return res
写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |