数组专题之区间问题
- 知识点：
- 解决思路：
- 例题
- 56.合并区间
- 57.插入区间
- 253.会议室 Ⅱ
- 485.无重叠区间
数组区间问题是算法中常见的一类问题，它们通常涉及对数组中的区间进行排序、合并、插入或删除操作。无论是合并区间、插入区间还是删除重复空间，首先都需要区分需要处理的区间的条件，主要是对区间左右边界的比较。以下是数组区间问题的知识点和解决思路的总结：
知识点：
- 区间表示：一个区间通常用两个数表示，第一个数是区间的起始点，第二个数是区间的结束点。
- 区间排序：如果区间的起始点不同，可以通过排序快速找到重叠的区间，在例题中使用了
Arrays.sort()，自定义比较器：
//按照数组区间的第一个元素排序
Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
//按照数组区间的第二个元素排序
Arrays.sort(intervals,(a,b) -> a[1]- b[1]);
- 合并区间：当两个区间的起始点不同，但一个区间的结束点大于或等于另一个区间的起始点时，这两个区间可以合并为一个区间。
- 插入区间：当需要将一个新的区间插入到已有的区间集合中时，需要考虑新区间与已有区间的关系，可能需要合并区间或调整区间顺序。
- 无重叠区间：当区间之间没有公共部分时，这些区间是无重叠的。
解决思路：
- 排序：对于区间问题，通常首先需要对区间进行排序，以便于后续操作。排序可以按照起始点进行，也可以按照结束点进行。
- 合并区间：（56）
- 遍历排序后的区间，检查当前区间是否可以与前一个区间合并。
- 如果可以合并，更新合并后的区间的起始点和结束点。
- 继续遍历，直到处理完所有区间。
- 插入区间：（57）
- 遍历排序后的区间，找到插入位置。
- 如果新区间与当前区间重叠，需要合并区间。
- 更新插入后的区间顺序。
- 继续遍历，直到处理完所有区间。
- 无重叠区间：（253、485）
- 遍历排序后的区间，检查当前区间是否与前一个区间重叠。
- 不重叠的条件是后一个区间的左边界大于等于前一个区间的右边界
在解决区间问题时，通常需要考虑区间的特殊性质，比如区间的大小、起始点和结束点等。此外，还需要注意边界条件，比如空区间、只有一个区间的情况等。通过以上知识点和解决思路，可以解决大多数基本的区间问题。
例题
56.合并区间
思路：
本题使用扫描线法来解决，首先要对二维数组进行排序，根据其中数组元素的第一个数字进行升序排列（这里代码里用了一种正则表达式的排序方法，会在知识点总结进行介绍），在排序完成之后进行扫描，有三种情况，我们将最前面的数组区间设置为[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() 方法按照二维数组中的第一个元素进行排序。
57.插入区间
思路：
根据题目要求可以将数组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][]);
}
}
253.会议室 Ⅱ
思路：
本题采用优先队列解决，使用一个升序排列的优先队列记录每个会议的结束时间，然后遍历数组，当后一个会议的开始时间大于前一个会议的结束时间时，说明两个会议并不冲突，此时前一个会议从优先队列中弹出，后一个会议加入优先队列；反之，前一个会议不弹出，并将后一个会议加入优先队列，可以看出此时队列的大小即为需要会议室的数量，最后处理完所有的会议后返回优先队列的大小即可。
时间复杂度：
这段代码的时间复杂度为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();
}
}
485.无重叠区间
思路：
本题需要得到移除区间的最小数量，得到一个不重叠的区间，这里首先将每个区间按照右边界来排序，因为右边界越小说明后面区间可以选择空间越大，这样移除的区间就是最少的。判断不是重叠区间的条件是区间的左边界大于等于上一个区间的右边界。
时间复杂度：
这段代码的时间复杂度为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;
}
}
