LeetCode|452. 用最少数量的箭引爆气球-贪心算法-Comparator比较器使用数据结构|leetcode

一、题目描述
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数。
二、解题
贪心算法这题主要是使用贪心算法，先将区间进行右区间升序排序，取第一个区间的右区间为第一支箭，若当前区间的左区间小于第一支箭的右区间，说明可以穿过当前区间，若大于第一支箭的右区间，则说明需要重新一支箭。
这里有个坑：

class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } //还是贪心算法 //先按照数组的右边界排序升序然后选择重合点 Arrays.sort(points,new Comparator(){ public int compare(int[] a,int[] b){ return a[1]-b[1]; }); //统计返回的弓箭数 int cnt = 1; int right = points[0][1]; for(int i=1; iright){ cnt++; right = points[i][1]; }else if(points[i][0] <= right){ //如果左边界小于等于右区间继续； continue; } } return cnt; } }

这个代码在运行的时候发现在一个示例中没有通过。

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

LeetCode|452. 用最少数量的箭引爆气球-贪心算法-Comparator比较器使用

文章图片

主要是右区间的差值非常大，会造成溢出，所以需要重新写Comparator比较器。
正确代码 1、Integer.compare 使用Integer.compare进行排序

class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } //还是贪心算法 //先按照数组的右边界排序升序然后选择重合点 Arrays.sort(points,new Comparator(){ public int compare(int[] a,int[] b){ return Integer.compare(a[1], b[1]); }); //统计返回的弓箭数 int cnt = 1; int right = points[0][1]; for(int i=1; iright){ cnt++; right = points[i][1]; }else if(points[i][0] <= right){ //如果左边界小于等于右区间继续； continue; } } return cnt; } }

2、Comparator使用 Comparator接口是很常用的一个排序接口，对数组或者List列表，或者Map(非hash)等排序是我们经常使用的一种处理数据的手段。
我们只需要重写compare方法即可实现排序。
int compare(Object o1, Object o2) 返回一个基本类型的整型
如果要按照升序排序，
则o1 小于o2，返回-1（负数），相等返回0，01大于02返回1（正数）
如果要按照降序排序
则o1 小于o2，返回1（正数），相等返回0，01大于02返回-1（负数）

class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } //还是贪心算法 //先按照数组的右边界排序升序然后选择重合点 Arrays.sort(points,new Comparator(){ public int compare(int[] a,int[] b){ if (a[1] > b[1]) { return 1; } else if (a[1] < b[1]) { return -1; } else { return 0; } }); //统计返回的弓箭数 int cnt = 1; int right = points[0][1]; for(int i=1; iright){ cnt++; right = points[i][1]; }else if(points[i][0] <= right){ //如果左边界小于等于右区间继续； continue; } } return cnt; } }

【LeetCode|452. 用最少数量的箭引爆气球-贪心算法-Comparator比较器使用】注意：
当然也可以使用Lambda表达式，但是Lambda表达式的效率有点低，直接写Comparator会比较快。

class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } //还是贪心算法 //先按照数组的右边界排序升序然后选择重合点 Arrays.sort(points,(a,b)->Integer.compare(a[1], b[1])); //统计返回的弓箭数 int cnt = 1; int right = points[0][1]; for(int i=1; iright){ cnt++; right = points[i][1]; }else if(points[i][0] <= right){ //如果左边界小于等于右区间继续； continue; } } return cnt; } }