代码训练(2)LeetCode之区间列表的交集
Author: Once Day Date: 2024年3月5日
漫漫长路，才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
- 986. 区间列表的交集 - 力扣（LeetCode）
- 力扣 (LeetCode) 全球极客挚爱的技术成长平台
文章目录
- 代码训练(2)LeetCode之区间列表的交集
- 1. 问题
- 2. 分析
- 3. 代码实现
- 3.1 代码具体含义解释
- 3.2 运行结果如下所示
- 4. 结论
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
也信美人终作土，不堪幽梦太匆匆......
如果这篇文章为您带来了帮助或启发，不妨点个赞👍和关注，再加上一个小小的收藏⭐！
(｡◕‿◕｡)感谢您的阅读与支持~~~
