Comparator之用最少数量的箭引爆气球

前言

今天刷个题，遇到一个很有趣的问题，关于Comparator的使用，感觉也是一个关于写代码的一些小细节的问题

关于Comparator

Comparator是java8新增的一个比较器，相信大家如果使用过Arrays和Collections的排序方法时，应该对这个都不陌生，不知道大家都是怎么写比较器内部的代码

这种写法应该也是大家会用的方法。

// 1. 第一种写法
Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
                
            }
        });
1
2
3
4
5
6
7
8
9
10
11

第二种写法，这种是调用compareTo方法，这种方法是用来比较Integer, Long, Short, Double，Byte类型

```java
// 1. 第一种写法
Arrays.sort(points, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
1
2
3
4
5
6
7

第三种写法，这种写法应该是非常常见的写法了。

```java
Arrays.sort(points, new Comparator() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0]) {
                    return -1;
                } else if (o1[0] > o2[0]) {
                    return 1;
                } else {
                    return 0;
                }        
            }
        });
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

原题

细心的同学就会发现了，第一种写法是有一定问题的，第二种方法的话有一定的局限性，为什么我会这么说呢，先看一道题吧LeetCode452:用最小数量的箭引爆气球这道题。

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，
其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知
道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出
一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足
  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。
 弓箭一旦被射出之后，可以无限地前进。给你一个数组 points ，返回引爆所有气球所必须
射出的 最小 弓箭数 。

1
2
3
4
5
6
7
8

这道题的思路也不是很难，我们可以先对气球的start进行一个排序，然后关于气球的重叠我们可以分为两种情况，主要分为不重叠的情况和重叠的情况，重叠的情况以两个重叠的右边界的最小值来充当边界，然后遍历就可以成功。

下面来看我第一次提交的代码

class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        if (n == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });
        int ans = 1;
        // 如果两个气球都有重叠，取两个重叠的最小值，如果两个没有重叠，直接加1
        for (int i = 1; i < n; i++) {
            if (points[i][0] > points[i-1][1]) {
                ans ++;
            } else {
                // have overlap min right side 
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }
        return ans;
    }
}
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

好像这样看来是没有什么问题的，但是提交呢，竟然不通过，然后看一下最后执行的输入

[[-2147483646,-2147483645],[2147483646,2147483647]]
1

我们定位一下错误，o1[0] - o2[0]这里是不是已经越界了呢，事实是确实已经越界了，具体的结果留给大家去试了。

我们采用第三种比较方法提交

class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        if (n == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0]) {
                    return -1;
                } else if (o1[0] > o2[0]) {
                    return 1;
                } else {
                    return 0;
                }        
            }
        });
        int ans = 1;
        // 如果两个气球都有重叠，取两个重叠的最小值，如果两个没有重叠，直接加1
        for (int i = 1; i < n; i++) {
            if (points[i][0] > points[i-1][1]) {
                ans++;
            } else {
                // have overlap min right side 
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }
        return ans;
    }
}
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

当然最后是A了，不过这个越界还卡了我好久，没有注意到越界问题…