赞
踩
Arrays.sort()
,自定义比较器://按照数组区间的第一个元素排序
Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
//按照数组区间的第二个元素排序
Arrays.sort(intervals,(a,b) -> a[1]- b[1]);
思路:
本题使用扫描线法来解决,首先要对二维数组进行排序,根据其中数组元素的第一个数字进行升序排列(这里代码里用了一种正则表达式的排序方法,会在知识点总结进行介绍),在排序完成之后进行扫描,有三种情况,我们将最前面的数组区间设置为[start,end]
,向后扫描:
后面的区间的starti
大于end
,那么直接将前一个区间加入结果集中
后面的区间的starti
小于end
,这里又会分出两种情况:
(1)后面的区间完全包含在前面的区间
(2)后面的区间的endi
大于前面区间的end
以上两种情况我们都需要将end
更新为最大的end
值,所以可以归结为一类
如果还是不太理解的话可以点击视频讲解-合并区间。
时间复杂度:
首先将区间按照起始时间排序,这需要O(nlogn)
的时间复杂度,然后遍历排序后的区间,维护一个当前区间的起始时间和结束时间。如果遇到与当前区间重叠的新区间,就更新当前区间的结束时间。如果遇到与当前区间不重叠的新区间,就把当前区间加入到结果列表中,然后更新当前区间的起始时间和结束时间,这个遍历过程需要O(n)
的时间复杂度。所以总的时间复杂度是O(nlogn) + O(n) =
O(nlogn)
。
代码实现:
class Solution { public int[][] merge(int[][] intervals) { //将ntervals按照数组元素的第一个数排序 Arrays.sort(intervals,(a,b) -> a[0] - b[0]); List<int[]> ans = new ArrayList<>(); int start = intervals[0][0]; int end = intervals[0][1]; for(int[] interval : intervals){ if(interval[0] > end){ ans.add(new int[]{start,end}); start = interval[0]; end = interval[1]; }else{ end = Math.max(end,interval[1]); } } ans.add(new int[]{start,end}); return ans.toArray(new int[ans.size()][]); } }
知识总结:
1.List的常见使用
//向List中添加元素 List.add(e) //根据索引获取元素 List.get(index) //按照索引删除 List.remove(index) //按照元素内容删除 List.remove(Object o) //判断List中是否包含某个元素,返回true或false List.contains(Object o) //使用element替换该索引处的值 List.set(index,element) //在该索引位置插入一个值 List.add(index,element) //返回该值的第一个索引 List.indexOf(Object o) //返回该值的最后一个索引 List.lastIndexOf(Object o) //截取List的部分元素, //注意这里时左闭右开,即fromIndex的值要包括,但是toIndex的值不包括,索引从0开始 List.subList(fromIndex, toIndex) //返回该List中的元素数 List.size() //对比两个List的所有元素是否相同 //两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象 List1.equals(List2) //判断List是否为空 List.isEmpty() //返回Iterator集合对象 List.iterator() //将List转换为字符串 List.toString() //将List转换为数组 List.toArray()
2.二维数组的排序
Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
intervals
是一个二维数组,每个元素都是一个包含两个整数的数组,表示一个时间区间的开始和结束时间。(a, b) -> a[0] - b[0]
是一个lambda表达式,用作排序的比较函数。它比较两个数组a
和b
的第一个元素,如果a[0]
小于b[0]
,则返回一个负数,表示a
应该排在b
前面。经过排序,intervals
数组中的时间区间会按照开始时间的升序排列。
为什么不能直接使用Arrays.sort(intervals)
呢?
由于 intervals
数组中的元素是 int[]
类型的数组。在这种情况下,直接使用 Arrays.sort(intervals)
是不正确的,因为 Java
默认使用数组元素的比较顺序进行排序,对于 int[]
类型来说,比较的是数组的引用,而不是数组中的元素。
对于一维数组,比如 int[]
类型,Arrays.sort()
方法可以直接使用,它会按照数组元素的自然顺序进行排序。
但是对于二维数组 int[][]
类型,情况就不太一样了。因为二维数组的元素是一维数组,所以 Arrays.sort()
默认是按照一维数组的引用进行排序的,而不是按照一维数组中的元素进行排序。
为了按照二维数组中的特定元素进行排序,需要提供一个自定义的比较器,例如 (a, b) -> a[0] - b[0]
,这样可以告诉 Arrays.sort()
方法按照二维数组中的第一个元素进行排序。
思路:
根据题目要求可以将数组intervals
分为三部分,第一部分为需要合并区间的左边部分,可以直接加入结果数组中,第二部分是需要和插入区间合并的区间,第三部分是合并后右侧剩下的区间,直接加入结果数组,区分每个部分的条件如下:
(1)左侧部分:所有数组元素的右边界应该小于插入元素的左边界(intervals[i][1] < newInterval[0]
)
(2)合并部分:所有数组元素的左边界应该小于插入元素的右边界(intervals[i][0] <= newInterval[1]
)
下面是一个简单画图说明;
时间复杂度:
这段代码的时间复杂度为O(n)
,其中n
是intervals
数组的长度。
代码实现:
class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> ans = new ArrayList<>(); int n = intervals.length; int i = 0; //加入合并区间左边部分的元素 while(i < n && intervals[i][1] < newInterval[0]){ ans.add(intervals[i++]); } //合并区间 if(i < n){ newInterval[0] = Math.min(intervals[i][0],newInterval[0]); while(i < n && intervals[i][0] <= newInterval[1]){ newInterval[1] = Math.max(intervals[i++][1],newInterval[1]); } } ans.add(newInterval); //处理剩下的元素,即合并区间右边的元素 while(i < n){ ans.add(intervals[i++]); } return ans.toArray(new int[ans.size() - 1][]); } }
思路:
本题采用优先队列解决,使用一个升序排列的优先队列记录每个会议的结束时间,然后遍历数组,当后一个会议的开始时间大于前一个会议的结束时间时,说明两个会议并不冲突,此时前一个会议从优先队列中弹出,后一个会议加入优先队列;反之,前一个会议不弹出,并将后一个会议加入优先队列,可以看出此时队列的大小即为需要会议室的数量,最后处理完所有的会议后返回优先队列的大小即可。
时间复杂度:
这段代码的时间复杂度为O(nlogn)
,其中n
是intervals
的长度。这是因为使用了优先队列来存储会议的结束时间,并进行了排序。优先队列的插入和删除操作的时间复杂度为O(logn)
,而插入和删除操作都被执行了n
次,所以总的时间复杂度为O(nlogn)
。
代码实现:
class Solution { public int[][] merge(int[][] intervals) { if(intervals.length == 0) return 0; //使用优先队列来存储会议的结束时间 //创建了一个容量为intervals.length的优先队列,按照整数元素的升序排列 PriorityQueue<Integer> ans = new PriorityQueue<>(intervals.length, (a , b) -> a - b); ans.offer(intervals[0][1]); for(int i = 1; i < intervals.length ;i++){ //会议不冲突时将其弹出,会议冲突时将冲突会议加入 //最终优先队列的大小即为需要会议室的数量 if(intervals[i][0] >= ans.peek()){ ans.poll(); } ans.offer(intervals[i][1]); } return ans.size(); } }
思路:
本题需要得到移除区间的最小数量,得到一个不重叠的区间,这里首先将每个区间按照右边界来排序,因为右边界越小说明后面区间可以选择空间越大,这样移除的区间就是最少的。判断不是重叠区间的条件是区间的左边界大于等于上一个区间的右边界。
时间复杂度:
这段代码的时间复杂度为O(nlogn)
,其中n
是intervals
数组的长度。代码中的Arrays.sort()
函数的时间复杂度为O(nlogn)
,排序完成后,遍历intervals
数组的时间复杂度是O(n)
,因此总的时间复杂度为O(nlogn)
。
代码实现:
class Solution { public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length < 2) return 0; //将数组按照右边升序排序 Arrays.sort(intervals,(a,b) -> a[1]- b[1]); int cnt = 1; int end = intervals[0][1]; //遍历数组,找到所有不重复的元素,条件是区间的左边界大于end //符合条件更新end值,并cnt+1 for(int i = 1; i < intervals.length;i++){ if(intervals[i][0] >= end){ end = intervals[i][1]; cnt++; } } //返回总数量减去不重叠区间的数量即为结果 return intervals.length - cnt; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。