宁波制作手机网站,在东营怎么建网站,建设门户网站申请报告,北京优秀网站建设文章目录 Tag题目来源题目解读解题思路方法一#xff1a;合并区间 其他语言python3 写在最后 Tag
【合并区间】【排序】【数组】 题目来源
452. 用最少数量的箭引爆气球 题目解读
每个气球都有一个占据x轴的一个范围#xff0c;在这个范围里射出一只箭就会引爆该气球… 文章目录 Tag题目来源题目解读解题思路方法一合并区间 其他语言python3 写在最后 Tag
【合并区间】【排序】【数组】 题目来源
452. 用最少数量的箭引爆气球 题目解读
每个气球都有一个占据x轴的一个范围在这个范围里射出一只箭就会引爆该气球现在有一堆排布好的气球试问引爆所有的气球至少需要多少支箭。 解题思路
方法一合并区间
气球都是以区间的形式给出的那么我们将有交集的区间进行合并然后剩下的区间每个区间都需要一只箭来引爆q
实现代码
class Solution {
public:int findMinArrowShots(vectorvectorint 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 1for i in range(1, n):if points[i][0] r:res 1else: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写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
