漯河市建设监理协会网站,南京有哪些做网站的公司,oa软件多少钱一套,域名网站建设方案452. 用最少数量的箭引爆气球 - 力扣#xff08;LeetCode#xff09;
算法#xff1a;
局部最优#xff1a;当气球出现重叠#xff0c;一起射#xff0c;所用弓箭最少。
全局最优#xff1a;把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠#xff0c;需要对… 452. 用最少数量的箭引爆气球 - 力扣LeetCode
算法
局部最优当气球出现重叠一起射所用弓箭最少。
全局最优把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠需要对数组进行排序。
从前向后或从后向前排序都可以
如果气球重叠了重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。 以题目示例 [[10,16],[2,8],[1,6],[7,12]]为例 可以看出首先第一组重叠气球一定是需要一个箭气球3的左边界大于了 第一组重叠气球的最小右边界所以再需要一支箭来射气球3了。
正确代码
class Solution {public int findMinArrowShots(int[][] points) {//排序Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));int count 1;for (int i 1; ipoints.length; i){//若无重叠countif (points[i][0] points[i-1][1]){count;}//有重叠更新最小右边届else{points[i][1] Math.min(points[i-1][1],points[i][1]);}}return count;}
}
注意
1.Integer拼写要正确
Lambda 表达式 (a, b) - Integer.compare(a[0], b[0]) 中的 a 和 b 分别代表数组中的两个元素Integer.compare(a[0], b[0]) 是比较这两个元素的第一个值的大小。
按照数组中每个元素的第一个值进行升序排序。在 Java 中Arrays.sort 方法默认是按照升序进行排序的。
2.左边界用points[i][0]表示右边界用points[i][1]表示
points[i][0] 表示二维数组 points 中第 i 个元素的第一个值而 points[i][1] 则表示二维数组 points 中第 i 个元素的第二个值。
时间空间复杂度
时间复杂度 : O(nlogn) 。
排序需要 O(nlogn) 的复杂度 空间复杂度 : O(logn) 。
java所使用的内置函数用的是快速排序需要 logn 的空间
