leetcode 452

老师你好针对leetcode的第 452题，Minimum Number of Arrows to Burst Balloons, 我的java题解如下，但是没能通过，没想出来为什么

class Solution {

public int findMinArrowShots(int[][] points) {

if(points.length == 0) return 0;

Arrays.sort(points, (a, b) -> a[1] - b[1]);

int close = points[0][1];

int arrow = 1;

for(int[] point : points) {

if(point[0] > close) {

close = point[1];

arrow++;

}

return arrow;

}

weixin_慕圣6334738 2021-09-06

源自：排序基础 1-1 最简单的排序算法：选择排序法

收起

1回答

liuyubobobo 2021-09-06 15:58:42

你这样给我贴一段代码问我为什么不对，我也不知道，因为我完全不明白你的代码思路。

请你：

1）简单阐述你的思路，并在代码重要的地方加注释；

2）对于什么测试用例，你的程序是错误的？对于这个测试用例，肯定在某一步，你的程序中变量计算的结果不正确了。具体是哪里？你的程序中的哪个变量存储的是什么？但你觉得实际应该是什么？你觉得想不明白？

如果你不知道如何找到你的程序的错误用例，将你的代码提交给 Leetcode，Leetcode 会返回出现错误的代码。比如我将你的程序提交后，返回是这样：

说明对于这个测试用例，正确答案是 2，你的程序返回结果是 1。

==========

其实很多时候，把这些“真正的问题”提出来，你很有可能已经自己解决了问题。

贴代码没有意义，讨论逻辑才有意义。不然我完全给你贴一个正确的代码，我相信这不是你想要的答案。

关于代码逻辑的描述和注释，可以参考这些问题：

https://class.imooc.com/course/qadetail/301612

https://class.imooc.com/course/qadetail/302016

继续加油！：）

收起回答

提问者 weixin_慕圣6334738 #1

谢谢老师的耐心回答～
我的思路如下（comment部分）我按照这个逻辑走了一个没通过的case，也就是上面您发的leetcode那个感觉也没什么问题：）

class Solution {
public int findMinArrowShots(int[][] points) {
if(points.length == 0) return 0;

/* 先将array按照里面所储存的每个子array的第二个数进行升序排序，我的解题思路是：在升序完成之后，判断后一个[]的第一个数，是不是比前一个[]的第二个数字
小，如果是的话说明区间是重复的，那么我们就不需要增加arrow的数量，如果后一个[]的第一个数比前一个[]大，那么我们就增加arrow的数量*/

/* 通过自定义sort来实现上面描述的排序方式*/
Arrays.sort(points, (a, b) -> a[1] - b[1]);

/* close代表的就是每个子array的第二个数*/
int close = points[0][1];
// arrow代表的就是所需要的弓箭数量
int arrow = 1;

// 对排好序的points进行遍历
for(int[] point : points) {
// 我们只有第二个list的前一个数比前面的list的后一个数字大时才增加arrow
if(point[0] > close) {
close = point[1];
arrow++;
}
}
return arrow;
}
}

2021-09-06 16:22:25
liuyubobobo 回复提问者 weixin_慕圣6334738 #2
你的逻辑是正确的。你的代码的错误在于，Arrays.sort 中使用了 a[1] - b[1]，而这个减法可能整形溢出。在截图的测试用例中，就发生了溢出的情况。整形溢出导致排序失败。你可以使用截图的测试用例在本地测试一下，在 sort 后，point 的排序结果是不正确的。

这样排序就 ok 了:
```
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
```
继续加油！：）
2021-09-07 01:19:23