区间问题

题目详情

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例1：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例2:

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路:

1. 先利用sort的Comparator自定义根据区间的左端点进行排序.
2. 排好序之后再进行遍历挨个进行判断,把区间逐个放入res的List中
3. 判断方法详细见代码注释
4. 最后别忘了返回类型是int[]要把List转化一下

我的代码：

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) return new int[0][2];//自定义Comparator来sort,根据二维数组的行从小到大排列Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2){return interval1[0] - interval2[0];}});//统计结果List<int[]> res = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i){//left:遍历到的区间的左端点  right:右端点int left = intervals[i][0], right = intervals[i][1];//因为数组排序过了,所以这里判断res最右边端点是否和遍历到的区间有重合即可//res中插入首元素    || 没重合,就将遍历到的放入resif (res.size() == 0 || res.get(res.size()-1)[1] < left){res.add(new int[]{left, right});}//有重合,合并两个区间:right如果比res最右边端点大,就要更新res中的最右端点为rightelse {res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], right);}}//注意将List转化为Array返回return res.toArray(new int[res.size()][]);}
}

ArrayList 的 sort的Comparator参数

在进行数组的排序时候,有时候默认的sort规则不能满足我们的要求,于是我们就要利用其中的Comparator参数来制定一个自定义排序规则.

说到Comparator,就免不了联想到Comparable,从字面看它们有相似的功能,确实,这两个接口都用于自定义比较规则

Comparable (java.lang.Comparable)

Comparable接口的定义非常简单

public interface Comparable<T> {int compareTo(T t);
}

很明显,如果你让一个类实现了Comparable接口,那么必须重写compareTo方法.我们自定义的比较规则也是在这个方法中实现的.

这里举个栗子.

public class Person implements Comparable<Person> {private String size;private String name;public Person(String size, String name) {this.size = size;this.name = name;}@Overridepublic int compareTo(Person o) {return this.getSzie() - o.getSize();}public static void main(String[] args) {Person XiaoHong = new Person("F","小红");Person XiaoMei = new Person("A","小美");if (XiaoHong.compareTo(XiaoMei) < 0) {System.out.println(XiaoHong.getName() + " 身材比较好");} else {System.out.println(XiaoMei.getName() + " 身材比较好");}}
}
//输出:小红 身材比较好

上面我们定义的Person类实例化的对象,我们想要通过它的一个字段来比较(size),所以我们重写了compareTo方法来实现,return的可能是负数,0,正数.这样我们就能根据A.compareTo(B)这样自定义比较(负数 : A小于B ; 0:A等于B ; 正数 : A大于B).

另外,如果我们不重写这个接口,比如:

List<String> list = new ArrayList<>();list.add("c");
list.add("b");
list.add("a");Collections.sort(list);

String实现了Comparable接口,这时它会逐个比较完成排序.

Comparator(java.util.Comparator)

同样的,该接口内也有两个核心方法

public interface Comparator<T> {int compare(T o1, T o2);boolean equals(Object obj);
}

第一个方法int compare(T o1, T o2);和上面的compareTo一样,也是返回负数;0;正数,从而实现自定义比较.

第二个方法boolean equals(Object obj);需要传入一个Object参数,并判断该参数是否和Comparator保持一致.

这时候,有人要说了,Comparator和Comparable这不都一样嘛,有啥区别啊

我们不妨想一下,如果我们只是临时想自定义一个比较规则来比较两个对象,但是又不想改变类(实现Comparatable接口)

那么这时候就可以利用Comparator了.

还是举个栗子.

public class Person {private String size;private String name;public Person(String size, String name) {this.size = size;this.name = name;}
}

这里我们就不需要去动Person类,直接写一个比较器实现Comparator接口即可

public class PersonComparatorBySize implements Comparator<Person> {@Overridepublic int compare(Person o1, Person o2) {return o1.getSize() - o2.getSize();}
}

当然也可以写一个比较器按照name进行自然排序.

public class PersonComparatorByName implements Comparator<Person> {@Overridepublic int compare(Person o1, Person o2) {if (o1.getName().hashCode() < o2.getName().hashCode()) {return -1;} else if (o1.getName().hashCode() == o2.getName().hashCode()) {return 0;}return 1;}
}

测试类:

Person XiaoHong = new Person("F","小红");
Person XiaoFang = new Person("E","小芳");
Person XiaoMei = new Person("A","小美");List<Person> list = new ArrayList<>();
list.add(XiaoHong);
list.add(XiaoFang);
list.add(XiaoMei);list.sort(new PersonComparatorBySzie());for (Person c : list) {System.out.println(c.getName());
}

我们通过把三个Person放入List中,再通过List的sort自定义比较器进行Size排序,同样实现了自定义需求.

使用 Comparator 和 Comparable 的场景汇总

使用Collection.sort排序列表/集合

对List或Collection进行排序时候,Collection那一个继承树里的所有类都有默认的Collection.sort()方法,该方法就是实现了Comparable接口来进行对象比较排序.

如果我们不想用默认提供的自然排序,就要给自己的Class实现Comparable接口了.

但是如果你又不想动自己的Class,那就要用到Comparator比较器了.而且这个比较器刚好还可以作为Collection.sort()方法的第二个参数.

Comparator 与 Stream 排序的结合使用

熟练了,我们就可以利用Stream来对集合元素进行排序,比使用sort方法更加灵活方便.

比如用元素中的某个字段为比较规则来进行正序倒序排序:

// 以元素对象的personId 为标准对集合进行正序排序
personList.stream().sorted(Comparator.comparing(Person::getPersonId)).forEach(person -> System.out.println(person.getName()));
// 以元素对象的personId 为标准对集合进行倒序排序
personList.stream().sorted(Comparator.comparing(Person::getPersonId).reversed()).forEach(person -> System.out.println(person.getName()));

甚至可以用多个字段进行多维排序:

// 先按personId 排序，再按 age 排序
personList.stream().sorted(Comparator.comparing(Person::getPersonId).thenComparing(Person::getAge)
).forEach(person -> System.out.println(person.getName()));