代码训练LeetCode(2)区间列表的交集

这篇具有很好参考价值的文章主要介绍了代码训练LeetCode(2)区间列表的交集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

代码训练(2)LeetCode之区间列表的交集

Author: Once Day Date: 2024年3月5日

漫漫长路,才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

  • 986. 区间列表的交集 - 力扣(LeetCode)
  • 力扣 (LeetCode) 全球极客挚爱的技术成长平台
1. 问题

给定两个由一些 闭区间 组成的列表,firstListsecondList ,其中 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]]

其区间如下所示:

代码训练LeetCode(2)区间列表的交集,CS小白之路,程序的艺术,#  十年代码训练,leetcode,算法,c语言

从图上可以看出,有交集的区间是[[1, 3], [4, 5], [6, 8], [9, 10]]

2. 分析

该问题是一个有点难度的编程题目,我们用C语言来实现,并且额外要求性能较高(速度90%,内存80%)。

想象你手中有两根彩色的绳子,这两根绳子由不同颜色的段落组成,每个颜色的段落代表一个闭区间。现在你的任务是找出这两根绳子中颜色相叠的部分,这些部分就是两组区间的交集。

(1) 原题解析

  • 两个列表都是由闭区间组成,已经根据区间的起点进行了排序。
  • 两个列表中的区间都是不相交的,也就是说列表内部不会有重叠的部分。
  • 我们需要返回的是两个列表中相互重叠区间的集合。

(2) 解题思路

  1. 使用两个指针分别遍历两个列表,初始时都指向各自列表的第一个区间。
  2. 对于每一对区间,比较它们的起点和终点来确定是否有交集。
  3. 如果有交集,计算出交集区间,并将其加入到结果集中。
  4. 移动指针来继续检测下一对可能重叠的区间,直到至少有一个列表被完全遍历。

(3) 分析步骤

  • 判断两个区间是否有交集的条件是,一个区间的起点小于或等于另一个区间的终点。
  • 交集区间的起点是两个区间起点的最大值,终点是两个区间终点的最小值。
  • 如果firstList的区间终点小于secondList的区间终点,移动firstList的指针;反之,则移动secondList的指针。

(4) 性能优化关键点

  • 执行速度:由于两个列表都已排序,我们可以利用这一点来减少不必要的比较,从而提高执行速度。
  • 内存使用:可以在原地记录结果,避免使用额外的内存空间。
3. 代码实现

假设firstList = [[1,3],[5,9]]secondList = [[2,4],[8,10]]

  1. 比较[1,3][2,4],有交集[2,3]
  2. 比较[5,9][2,4],没有交集,[2,4]的终点小,移动secondList指针。
  3. 比较[5,9][8,10],有交集[8,9]
  4. 结果集为[[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 代码具体含义解释

上面代码可以计算两个列表 firstListsecondList 中表示的区间集合的交集。每个列表中的每个区间都由一对整数表示,这对整数分别标示了区间的开始和结束。列表中的区间已经以升序排列,并且在单个列表内,区间不会重叠和相连。

函数的参数解释如下:

  • int** firstList:指向第一个区间列表的指针。
  • int firstListSize:第一个列表中区间的数量。
  • int* firstListColSize:指向一个数组,其中每个元素表示 firstList 中对应区间的大小(在这个场景中,每个区间由两个整数组成,所以该数组的每个元素应该都是 2)。
  • int** secondList:指向第二个区间列表的指针。
  • int secondListSize:第二个列表中区间的数量。
  • int* secondListColSize:指向一个数组,其中每个元素表示 secondList 中对应区间的大小(同样,每个元素应该都是 2)。
  • int* returnSize:指向一个整数的指针,该整数表示交集列表中区间的数量。
  • int** returnColumnSizes:指向一个指针的指针,用来分配和返回交集列表中每个区间的大小。

函数的主要逻辑如下:

  1. 动态分配内存空间给 result,这是用来存储区间交集结果的指针数组。大小为两个列表大小之和,这是因为最坏的情况下,交集的数量可能等于两个列表中区间数量之和。
  2. 动态分配内存空间给 *returnColumnSizes,用来存储每个交集区间的大小(在本函数中,每个交集区间大小都是 2)。
  3. 使用两个索引 ij 分别遍历 firstListsecondListk 用来记录 result 中交集区间的数量。
  4. 使用宏 MaxMin 来计算两个区间的最大开始点和最小结束点,以确定它们是否有交集。
  5. 如果两个区间有交集(startMax <= endMin),则将这个交集区间存储在 result[k] 中,并且将 (*returnColumnSizes)[k] 设置为 2,然后递增 k
  6. 然后,比较两个区间的结束点,将结束较早的区间的索引(ij)递增,以移动到下一个区间。
  7. 重复步骤 4 到 6,直到任一列表全部遍历完。
  8. 设置 *returnSizek,即交集区间的实际数量。
  9. 返回 result,它指向包含所有交集区间的指针数组。

函数结束后,调用者将得到一个包含所有交集区间的数组 result,以及两个输出值:*returnSize 表示 result 中区间的数量,*returnColumnSizes 表示 result 中每个区间的大小。调用者需要负责释放 result 数组和 *returnColumnSizes 数组的堆内存。

3.2 运行结果如下所示

代码训练LeetCode(2)区间列表的交集,CS小白之路,程序的艺术,#  十年代码训练,leetcode,算法,c语言

从运行速率来看,离预定目标还差一些,我们来简单分析一下热点代码

除了一开始分配了大量内存之外,后续每次找到交集,都需要分配新内存,因此有大量的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: 指向数组的指针,该数组将包含结果中每个区间的大小。

函数的主要步骤如下:

  1. 分配内存以存储结果的区间列表。
  2. 如果两个列表中任何一个的大小为0,立即返回空的结果。
  3. 分配内存来存储结果列表中每个区间的大小。
  4. 使用两个指针ij遍历两个列表,寻找交集。
  5. 对每一对潜在的交集区间,检查它们是否相交,如果相交,计算交集并将其添加到结果列表中。
  6. 如果两个区间有交集,那么将交集区间添加到结果列表中,并递增对应的列表指针。
  7. 如果两个区间没有交集,递增指向较早开始区间的列表指针。
  8. 遍历结果列表,为每个区间设置大小为2(因为区间由一对整数表示)。
  9. 设置返回的区间数量。
  10. 返回结果列表。

有一点需要注意的是,这个函数在找到交集时并没有创建新的区间,而是直接使用了原列表中的指针。这意味着结果列表中的区间指针指向了firstListsecondList中的原始区间,可能在必要时修改了原始区间的起始点以反映交集的起始点。

这段代码重点在于如下几点

  1. 在一开始通过判断将特殊情况排除,可以提高部分场景的性能。
  2. 原地修改数据节点,不申请内存,因此效率较高,且内存使用较少。
  3. 优化判断逻辑,将主要判断提到开始,减少不必要判断。

下面是运行测试数据,成功达到预期性能目标:

代码训练LeetCode(2)区间列表的交集,CS小白之路,程序的艺术,#  十年代码训练,leetcode,算法,c语言

4. 结论

这个问题就像是找出两根彩色绳子中相同颜色覆盖的部分。我们通过设置两个指针,分别在两个列表上移动,寻找可能重叠的区间。计算可能的交集,并且根据区间终点的大小决定移动哪个指针。这种方法因为没有使用额外的数据结构,所以在内存使用上非常经济,同时由于两个列表的有序性,使得我们能够以线性的时间复杂度完成遍历,保证了算法的执行效率。通过这种方式,我们可以得到一个包含所有交集区间的列表,这正是题目所要求的结果。







代码训练LeetCode(2)区间列表的交集,CS小白之路,程序的艺术,#  十年代码训练,leetcode,算法,c语言

Once Day

也信美人终作土,不堪幽梦太匆匆......

如果这篇文章为您带来了帮助或启发,不妨点个赞👍和关注,再加上一个小小的收藏⭐!

(。◕‿◕。)感谢您的阅读与支持~~~文章来源地址https://www.toymoban.com/news/detail-839064.html

到了这里,关于代码训练LeetCode(2)区间列表的交集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • python 计算列表的交集,并集,差集

    如果是列表的话,先将列表转为集合,使用集合去操作,返回的结果也为集合 比如两个列表: 1. 并集,就是a和b的所有元素 2. 差集,b有,a没有的元素 3. 交集,ab共有的元素 4. 对称差集,a和b所有不属于set(b) set(a)的集合

    2024年02月15日
    浏览(56)
  • 代码训练LeetCode(15)买卖股票

    代码训练(15)LeetCode之买卖股票 Author: Once Day Date: 2024年4月22日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 122. 买卖股票的最佳时机 II - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 给你一个整数数组

    2024年04月27日
    浏览(23)
  • 代码训练LeetCode(6)编辑距离

    代码训练(6)LeetCode之编辑距离 Author: Once Day Date: 2024年3月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 72. 编辑距离 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 给你两个单词 word1 和 word2 , 请返回

    2024年03月12日
    浏览(30)
  • 代码训练LeetCode(14)整数反转

    代码训练(14)LeetCode之整数反转 Author: Once Day Date: 2024年4月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 190. 颠倒二进制位 - 力扣(LeetCode) 7. 整数反转 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题

    2024年04月27日
    浏览(27)
  • 代码训练LeetCode(5)最长连续序列

    代码训练(5)LeetCode之最长连续序列 Author: Once Day Date: 2024年3月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 128. 最长连续序列 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 给定一个未排序的整数数组

    2024年03月24日
    浏览(37)
  • 代码训练LeetCode(12)二进制求和

    Author: Once Day Date: 2024年3月14日 一位热衷于Linux学习和开发的菜鸟,试图谱写一场冒险之旅,也许终点只是一场白日梦… 漫漫长路,有人对你微笑过嘛… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 67. 二进制求和 - 力扣(LeetCode) 力扣 (LeetCode) 全球极

    2024年03月20日
    浏览(46)
  • 代码训练LeetCode(13)颠倒二进制位

    代码训练(13)LeetCode之颠倒二进制位 Author: Once Day Date: 2024年4月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 190. 颠倒二进制位 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 颠倒给定的 32 位无符号整

    2024年04月27日
    浏览(44)
  • 代码训练LeetCode(9)Git自动同步脚本

    代码训练(9)LeetCode之Git自动同步脚本 Author: Once Day Date: 2024年3月10日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: Git使用记录_Once-Day的博客-CSDN博客 1. 题目 这个题目是自拟的,来自于个人开发过程中的需求: 写段bash脚本,同步

    2024年03月17日
    浏览(44)
  • 两个数组的交集(LeetCode 349)

    题目 349. 两个数组的交集  思路         将较长的序列放入一个set后,再加入短序列的数字,判断当前数字是否添加成功,如果添加成功则表示set中没有该数字,则不属于两个数组之间的交集,将该数字从set中移除(移除是因为保证set的纯洁性 即只含有长序列中的数字);

    2024年02月11日
    浏览(49)
  • LeetCode349. 两个数组的交集

    数组哈希.无序set都可以 给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通

    2024年01月23日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包