题目的链接在这里:https://leetcode-cn.com/problems/interval-list-intersections/
目录
题目大意
给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的,并且 已经排序 。返回这 两个区间列表的交集 。
形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b 。
两个闭区间的 交集 是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
一、示意图
二、解题思路
正常逻辑
正常逻辑
代码如下:
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
//先进行边界判断
if(firstList.length==0||secondList.length==0){
return new int[0][];
}
//参考昨天的方法 先写一个存储的数组
List<int[]> res=new LinkedList<>();
int fir=0;
int sed=0;
while (fir<firstList.length&&sed<secondList.length){
//需要进行四个比较吗 头和头 头和尾 尾和头 尾和尾
//直接判断 first的尾巴在不在 sec的头尾之间?
if(firstList[fir][1]>=secondList[sed][0]&&firstList[fir][1]<=secondList[sed][1]){
//说明在 头尾之间 那就需要判断fir的头和sec的头之间的大小了
if(firstList[fir][0]>=secondList[sed][0]){
//说明firs更大
//那他们的交集肯定是 那就是需要fir的头和尾
//然后怎么改进呢
res.add(new int[]{firstList[fir][0], firstList[fir][1]});
//这两个都说明 first比sec要小了
fir++;
//sec不要移动吧
}else{
//那肯定就是 那就说明是 sec的更大了 而更大表示范围更小
if(secondList[sed][0]<=firstList[fir][1]){
res.add(new int[]{secondList[sed][0], firstList[fir][1]});
}
fir++;
}
}else if(firstList[fir][1]<secondList[sed][0]){
//那就说明fir都远远离开sec
fir++;
}else if(firstList[fir][1]>secondList[sed][1]){
//这里出现了判断 很有可能头尾都不接 那就直接头尾进行判断吧
//那就说明first至少包括了当前的sec
if(firstList[fir][0]>=secondList[sed][0]){
//如果first 比较大的话 更好证明 fir的范围更小
if(firstList[fir][0]<=secondList[sed][1]) {
res.add(new int[]{firstList[fir][0], secondList[sed][1]});
}
//然后进行修改
sed++;
}else{
//这才说明是 sec的头尾
res.add(new int[]{secondList[sed][0], secondList[sed][1]});
sed++;
}
}
}
/**
* list的toArray 方法:里面有参数 res是一个list 他每一个都有一个数组 相当于他是数组的第一列 而每一列存储的 就是 数组对应的值
* 相当于 最后返回的 就是这个 new出来的Int 而这个int中存在 res对应的值
* public <T> T[] toArray(T[] a) {
* if (a.length < size)
* a = (T[])java.lang.reflect.Array.newInstance(
* a.getClass().getComponentType(), size);
* int i = 0;
* Object[] result = a;
* for (Node<E> x = first; x != null; x = x.next)
* result[i++] = x.item;
*
* if (a.length > size)
* a[size] = null;
*
* return a;
* }
*/
return res.toArray(new int[res.size()][]);
}
}