代码训练(2)LeetCode之区间列表的交集
Author: Once Day Date: 2024年3月5日
漫漫长路,才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
- 986. 区间列表的交集 - 力扣(LeetCode)
- 力扣 (LeetCode) 全球极客挚爱的技术成长平台
1. 问题
给定两个由一些 闭区间 组成的列表,
firstList
和secondList
,其中firstList[i] = [starti, endi]
而secondList[j] = [startj, endj]
。每个区间列表都是成对 不相交 的,并且 已经排序 。返回这 两个区间列表的交集 。
形式上,闭区间
[a, b]
(其中a <= b
)表示实数x
的集合,而a <= x <= b
。两个闭区间的 交集 是一组实数,要么为空集,要么为闭区间。例如,
[1, 3]
和[2, 4]
的交集为[2, 3]
。
比如对于以下两个区间:
firstList = [[1, 8], [9, 12]]
secondList = [[0, 3], [4, 5], [6, 10]]
其区间如下所示:
从图上可以看出,有交集的区间是[[1, 3], [4, 5], [6, 8], [9, 10]]
。
2. 分析
该问题是一个有点难度的编程题目,我们用C语言来实现,并且额外要求性能较高(速度90%,内存80%)。
想象你手中有两根彩色的绳子,这两根绳子由不同颜色的段落组成,每个颜色的段落代表一个闭区间。现在你的任务是找出这两根绳子中颜色相叠的部分,这些部分就是两组区间的交集。
(1) 原题解析:
- 两个列表都是由闭区间组成,已经根据区间的起点进行了排序。
- 两个列表中的区间都是不相交的,也就是说列表内部不会有重叠的部分。
- 我们需要返回的是两个列表中相互重叠区间的集合。
(2) 解题思路:
- 使用两个指针分别遍历两个列表,初始时都指向各自列表的第一个区间。
- 对于每一对区间,比较它们的起点和终点来确定是否有交集。
- 如果有交集,计算出交集区间,并将其加入到结果集中。
- 移动指针来继续检测下一对可能重叠的区间,直到至少有一个列表被完全遍历。
(3) 分析步骤:
- 判断两个区间是否有交集的条件是,一个区间的起点小于或等于另一个区间的终点。
- 交集区间的起点是两个区间起点的最大值,终点是两个区间终点的最小值。
- 如果
firstList
的区间终点小于secondList
的区间终点,移动firstList
的指针;反之,则移动secondList
的指针。
(4) 性能优化关键点:
- 执行速度:由于两个列表都已排序,我们可以利用这一点来减少不必要的比较,从而提高执行速度。
- 内存使用:可以在原地记录结果,避免使用额外的内存空间。
3. 代码实现
假设firstList = [[1,3],[5,9]]
,secondList = [[2,4],[8,10]]
。
- 比较
[1,3]
和[2,4]
,有交集[2,3]
。 - 比较
[5,9]
和[2,4]
,没有交集,[2,4]
的终点小,移动secondList
指针。 - 比较
[5,9]
和[8,10]
,有交集[8,9]
。 - 结果集为
[[2,3],[8,9]]
。
下面是C语言的实现代码:
int** intervalIntersection(int** firstList, int firstListSize, int* firstListColSize, int** secondList, int secondListSize, int* secondListColSize, int* returnSize, int** returnColumnSizes) {
int **result = malloc(sizeof(int *) * (firstListSize + secondListSize));
*returnColumnSizes = malloc(sizeof(int) * (firstListSize + secondListSize));
int i = 0, j = 0, k = 0;
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
while (i < firstListSize && j < secondListSize) {
int startMax = Max(firstList[i][0], secondList[j][0]);
int endMin = Min(firstList[i][1], secondList[j][1]);
if (startMax <= endMin) { // There is an intersection
result[k] = malloc(sizeof(int) * 2);
result[k][0] = startMax;
result[k][1] =endMin;
(*returnColumnSizes)[k++] = 2;
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
*returnSize = k;
return result;
}
3.1 代码具体含义解释
上面代码可以计算两个列表 firstList
和 secondList
中表示的区间集合的交集。每个列表中的每个区间都由一对整数表示,这对整数分别标示了区间的开始和结束。列表中的区间已经以升序排列,并且在单个列表内,区间不会重叠和相连。
函数的参数解释如下:
-
int** firstList
:指向第一个区间列表的指针。 -
int firstListSize
:第一个列表中区间的数量。 -
int* firstListColSize
:指向一个数组,其中每个元素表示firstList
中对应区间的大小(在这个场景中,每个区间由两个整数组成,所以该数组的每个元素应该都是 2)。 -
int** secondList
:指向第二个区间列表的指针。 -
int secondListSize
:第二个列表中区间的数量。 -
int* secondListColSize
:指向一个数组,其中每个元素表示secondList
中对应区间的大小(同样,每个元素应该都是 2)。 -
int* returnSize
:指向一个整数的指针,该整数表示交集列表中区间的数量。 -
int** returnColumnSizes
:指向一个指针的指针,用来分配和返回交集列表中每个区间的大小。
函数的主要逻辑如下:
- 动态分配内存空间给
result
,这是用来存储区间交集结果的指针数组。大小为两个列表大小之和,这是因为最坏的情况下,交集的数量可能等于两个列表中区间数量之和。 - 动态分配内存空间给
*returnColumnSizes
,用来存储每个交集区间的大小(在本函数中,每个交集区间大小都是 2)。 - 使用两个索引
i
和j
分别遍历firstList
和secondList
,k
用来记录result
中交集区间的数量。 - 使用宏
Max
和Min
来计算两个区间的最大开始点和最小结束点,以确定它们是否有交集。 - 如果两个区间有交集(
startMax
<=endMin
),则将这个交集区间存储在result[k]
中,并且将(*returnColumnSizes)[k]
设置为 2,然后递增k
。 - 然后,比较两个区间的结束点,将结束较早的区间的索引(
i
或j
)递增,以移动到下一个区间。 - 重复步骤 4 到 6,直到任一列表全部遍历完。
- 设置
*returnSize
为k
,即交集区间的实际数量。 - 返回
result
,它指向包含所有交集区间的指针数组。
函数结束后,调用者将得到一个包含所有交集区间的数组 result
,以及两个输出值:*returnSize
表示 result
中区间的数量,*returnColumnSizes
表示 result
中每个区间的大小。调用者需要负责释放 result
数组和 *returnColumnSizes
数组的堆内存。
3.2 运行结果如下所示
从运行速率来看,离预定目标还差一些,我们来简单分析一下热点代码。
除了一开始分配了大量内存之外,后续每次找到交集,都需要分配新内存,因此有大量的malloc操作,在C语言里,分配内存是相对耗时较久的任务。
该问题获取交集时,对于两个比较的集合元素,总是取其中一个元素用于下一轮比较,那么此时。另外一个元素就可以用来存储可能得闭区间。此外优化数组访问和比较流程,减少指令数,如下:
int** intervalIntersection(int** firstList, int firstListSize, int* firstListColSize, int** secondList, int secondListSize, int* secondListColSize, int* returnSize, int** returnColumnSizes) {
int **result = malloc(sizeof(int *) * (firstListSize + secondListSize));
if (firstListSize ==0 || secondListSize == 0) {
*returnSize=0;
return result;
}
*returnColumnSizes = malloc(sizeof(int) * (firstListSize + secondListSize));
int i = 0, j = 0, k = 0;
while (i < firstListSize && j < secondListSize) {
int *first = firstList[i];
int *second = secondList[j];
if (first[0] <= second[1] && second[0] <= first[1]) {
if (first[1] <= second[1]) {
if (second[0] > first[0]) {
first[0] = second[0];
}
i++;
result[k++] = first;
} else {
if (second[0] < first[0]) {
second[0] = first[0];
}
j++;
result[k++] = second;
}
} else {
if (first[0] < second[0]) {
i++;
} else {
j++;
}
}
}
int *temp = *returnColumnSizes;
for (i = 0; i < k; i++) {
temp[i] = 2;
}
*returnSize = k;
return result;
}
函数的参数解释如下:
-
int** firstList
: 指向第一个区间列表的指针。 -
int firstListSize
: 第一个列表中区间的数量。 -
int* firstListColSize
: 指向数组的指针,其中包含firstList
中每个区间的大小。 -
int** secondList
: 指向第二个区间列表的指针。 -
int secondListSize
: 第二个列表中区间的数量。 -
int* secondListColSize
: 指向数组的指针,其中包含secondList
中每个区间的大小。 -
int* returnSize
: 指向结果的区间数量的指针。 -
int** returnColumnSizes
: 指向数组的指针,该数组将包含结果中每个区间的大小。
函数的主要步骤如下:
- 分配内存以存储结果的区间列表。
- 如果两个列表中任何一个的大小为0,立即返回空的结果。
- 分配内存来存储结果列表中每个区间的大小。
- 使用两个指针
i
和j
遍历两个列表,寻找交集。 - 对每一对潜在的交集区间,检查它们是否相交,如果相交,计算交集并将其添加到结果列表中。
- 如果两个区间有交集,那么将交集区间添加到结果列表中,并递增对应的列表指针。
- 如果两个区间没有交集,递增指向较早开始区间的列表指针。
- 遍历结果列表,为每个区间设置大小为2(因为区间由一对整数表示)。
- 设置返回的区间数量。
- 返回结果列表。
有一点需要注意的是,这个函数在找到交集时并没有创建新的区间,而是直接使用了原列表中的指针。这意味着结果列表中的区间指针指向了firstList
或secondList
中的原始区间,可能在必要时修改了原始区间的起始点以反映交集的起始点。
这段代码重点在于如下几点:
- 在一开始通过判断将特殊情况排除,可以提高部分场景的性能。
- 原地修改数据节点,不申请内存,因此效率较高,且内存使用较少。
- 优化判断逻辑,将主要判断提到开始,减少不必要判断。
下面是运行测试数据,成功达到预期性能目标:
4. 结论
这个问题就像是找出两根彩色绳子中相同颜色覆盖的部分。我们通过设置两个指针,分别在两个列表上移动,寻找可能重叠的区间。计算可能的交集,并且根据区间终点的大小决定移动哪个指针。这种方法因为没有使用额外的数据结构,所以在内存使用上非常经济,同时由于两个列表的有序性,使得我们能够以线性的时间复杂度完成遍历,保证了算法的执行效率。通过这种方式,我们可以得到一个包含所有交集区间的列表,这正是题目所要求的结果。
Once Day
也信美人终作土,不堪幽梦太匆匆......
如果这篇文章为您带来了帮助或启发,不妨点个赞👍和关注,再加上一个小小的收藏⭐!文章来源:https://www.toymoban.com/news/detail-839064.html
(。◕‿◕。)感谢您的阅读与支持~~~文章来源地址https://www.toymoban.com/news/detail-839064.html
到了这里,关于代码训练LeetCode(2)区间列表的交集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!