Leetcode452 打气球

2019-05-20

题目介绍

用二维数组表示二维平面中的气球，[start,end]分别表示气球的起始x坐标和终止位置x坐标，从底部垂直向上射击可以刺破所有[start,end]在射击坐标范围内的气球。最少射出多少支箭可以刺破所有的气球。
题目链接:https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/submissions/

思路

既然所有的气球都是要刺破的，对于某一个气球来说，在哪一个位置刺破可以顺带刺破的其他气球越多，就是刺破这个气球的最佳位置。 统计所有的“最佳位置”，就可以得出最终答案。
对所有的气球排序，排序按照终止位置end从小到大,则从头遍历所有气球，刺破第一个气球的“最佳射击点”就是第一个气球end位置，同时清除顺带刺破的其他气球以后，下一个“最佳射击点”就是下一个气球的end位置..统计射击的次数，就是最终答案。

代码

在代码实现上，此题需要着重考虑的问题是:

• 如果对二维数组按照特定的规则进行排序
  本题需要排序的二维数组形式是[[1,2],[3,4]]，排序依据各个子数组index=1的数字的大小。
  思路是，定义一个class Pair, Pair第一个元素表示二维数组中的子数组的位置索引，第二个元素表示子数组index=1位置的数组。将这些Pair全部存储在List中，最终对Pair按照第二个元素的大小排序。 排序后遍历List,Pair第一个元素存储的就是在原二维数组中排序后的气球的索引。找出来，将他们放置在一个新的二维数组中就完成了气球的排序。
  代码:

class Pair {
        private Integer k1;
        private Integer k2;
        public Pair(Integer k1, Integer k2) {
            this.k1 = k1;
            this.k2 = k2;
        }
    }
    public int findMinArrowShots(int[][] points) {
        if(points.length == 0 ) return 0;
        // 对气球的位置排序排序
        List<Pair> pairs = new ArrayList<>();
        int[][] sp = new int[points.length][];
        int i = 0;
        for (int[] point : points) {
            pairs.add(new Pair(i++, point[1]));
        }
        Collections.sort(pairs, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return Integer.compare(o1.k2, o2.k2);
            }
        });
        for (int j = 0; j < points.length; j++) {
            sp[j] = points[pairs.get(j).k1].clone();
        }
        // SP是points按照point[1]的大小顺序排列的，上面的代码能不能精简一些?
        int ans = 1;
        int end = sp[0][1];
        for (int[] aSp : sp) {
            if (end < aSp[0]) {
                ans++;
                end = aSp[1];
            }
        }
        return ans;
    }

上述代码为自己写的版本，运行时间50%，运行内存10%。
排序代码太丑，不够优雅。
排序代码可以一行搞定

 int find2(int[][] points) {
        if (null == points || points.length == 0) return 0;
        Arrays.sort(points, Comparator.comparingInt(o -> o[0]));
        int ans = 1;
        int end = points[0][1];
        for (int[] p : points) {
            if (p[0] > end) {
                ans++;
                end = p[1];
            } else {
                end = Math.min(p[1], end);
            }
        }
        return ans;
    }