【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3197字，纯文字阅读大概需要5分钟。
内容图文
【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA）
题目地址: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
题目描述：
There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.
Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Example 2:
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Example 4:
Input: points = [[1,2]]
Output: 1
Example 5:
Input: points = [[2,3],[2,3]]
Output: 1
Constraints:
- 0 <= points.length <= 10^4
- points[i].length == 2
- -2^31 <= xstart < xend <= 2^31 - 1
题目大意
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
解题方法
123456789
23456
6789
7891234
- 先对 points 二维数组进行排序
- 从头开始，判断射出的第一支箭在什么地方
- 为了射出尽可能少的箭，当然应该在重合的最后一个地方：从第一个数组的开始，然后往后遍历找到 points[i][1] 最小的记录下为 max，如果下一个 points[i][0] 比 max 小就结束，前面应该射一箭了
- note: -2^31 <= xstart < xend <= 2^31 - 1, 在排序的时候不能采用 a[0] - b[0] 的运算，int 会超限
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length <= 1) return points.length;
Arrays.sort(points, (a, b) -> {
if (a[0] == b[0]) {
if (a[1] == b[1]) return 0;
if (a[1] < b[1]) return -1;
return 1;
} else if (a[0] < b[0]) {
return -1;
}
return 1;
});
int next = 0;
int res = 0;
do {
next = nextIndex(points, next);
res++;
} while (next < points.length);
return res;
}
public int nextIndex(int[][] points, int start) {
if (start >= points.length) return start;
int max = points[start][1];
for (int i = start + 1; i < points.length; i++) {
if (points[i][0] > max) return i;
max = Math.min(max, points[i][1]);
}
return points.length;
}
}
执行耗时:21 ms,击败了76.19% 的Java用户
内存消耗:46 MB,击败了83.75% 的Java用户
内容总结
以上是互联网集市为您收集整理的【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA）全部内容，希望文章能够帮你解决【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。