题目
结果
代码
超时算法（不看也罢）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public int findMinArrowShots(int[][] points) {
List<List<Integer>> intervals = new ArrayList<>();
for (var xy : points) {
intervals.add(List.of(xy[0], xy[1]));
}
int arrows = 0;
while (!intervals.isEmpty()) {
var intersection = intersection(intervals, intervals.get(0));
if (intersection != null) {
intervals.remove((int) intersection.get(2));
intervals.remove(0);
intervals.add(List.of(intersection.get(0), intersection.get(1)));
} else {
intervals.remove(0);
arrows++;
}
}
return arrows;
}
private List<Integer> intersection(List<List<Integer>> intervals, List<Integer> range) {
if (intervals.size() == 1) {
return null;
}
for (int i = 1; i < intervals.size(); i++) {
var interval = intervals.get(i);
if (interval.get(0).equals(range.get(0))) {
return List.of(interval.get(0), Math.min(interval.get(1), range.get(1)), i);
}
if (interval.get(1).equals(range.get(1))) {
return List.of(Math.max(interval.get(0), range.get(0)), range.get(1), i);
}
if (interval.get(1) < range.get(0) || range.get(1) < interval.get(0)) {
continue;
} else {
return List.of(Math.max(interval.get(0), range.get(0)), Math.min(interval.get(1), range.get(1)), i);
}
}
return null;
}
}
|
龟速算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int findMinArrowShots(int[][] points) {
List<List<Integer>> intervals = new ArrayList<>();
for (var xy : points) {
intervals.add(List.of(xy[0], xy[1]));
}
intervals.sort(Comparator.comparingInt(interval -> interval.get(1)));
int arrows = 0;
while (!intervals.isEmpty()) {
shoot(intervals, intervals.get(0).get(1));
arrows++;
}
return arrows;
}
private void shoot(List<List<Integer>> intervals, int num) {
List<Integer> targets = new ArrayList<>();
for (int i = 0; i < intervals.size(); i++) {
var interval = intervals.get(i);
if (num >= interval.get(0) && num <= interval.get(1)) {
targets.add(i);
}
}
for (int i = targets.size() - 1; i >= 0; i--) {
intervals.remove((int) targets.get(i));
}
}
}
|
极速算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, Comparator.comparingInt(point -> point[1]));
int pos = points[0][1];
int arrows = 1;
for (var xy : points) {
if (xy[0] > pos) {
arrows++;
pos = xy[1];
}
}
return arrows;
}
}
|
算法思路：贪心算法。
数组中有若干个区间——[a1,b1],[a2,b2]……[an,bn]，每次选择Min（b1~bn）这个点，删除包含这个点的区间，并且arrows+1，最终得到的arrows就是结果。
为什么Min(b1~bn)是最优解？可以逆向想一下，往左移动可能会减少捅破的气球，往右则这个区间的气球不能被捅到。
复杂度
时间复杂度：O（nlogn）
空间复杂度：O（logn），Arrays.sort的空间复杂度