力扣第 56 题 合并区间

embedded/2024/11/20 11:45:50/

解法思路

  1. 区间排序

    • 按区间的起点升序排序。
    • 如果起点相同,则按终点升序排序。
  2. 遍历合并

    • 使用一个动态数组存储合并后的结果。
    • 遍历排序后的区间:
      • 如果当前区间的起点在结果数组最后一个区间的终点后,直接加入结果数组。
      • 否则,更新结果数组最后一个区间的终点为两者终点的最大值。
  3. 返回结果

    • 返回合并后的区间数组及其长度。

C 语言解法

#include <stdio.h>
#include <stdlib.h>// 比较函数,用于按起点排序区间
int compare(const void* a, const void* b) {int* intervalA = *(int**)a;int* intervalB = *(int**)b;if (intervalA[0] != intervalB[0]) {return intervalA[0] - intervalB[0];}return intervalA[1] - intervalB[1];
}// 合并区间函数
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {if (intervalsSize == 0) {*returnSize = 0;*returnColumnSizes = NULL;return NULL;}// 按起点排序区间qsort(intervals, intervalsSize, sizeof(int*), compare);// 动态分配结果数组int** result = (int**)malloc(intervalsSize * sizeof(int*));*returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));int count = 0;// 初始化第一个区间result[count] = (int*)malloc(2 * sizeof(int));result[count][0] = intervals[0][0];result[count][1] = intervals[0][1];(*returnColumnSizes)[count] = 2;// 遍历区间进行合并for (int i = 1; i < intervalsSize; i++) {if (intervals[i][0] <= result[count][1]) {// 合并区间result[count][1] = (intervals[i][1] > result[count][1]) ? intervals[i][1] : result[count][1];} else {// 新区间count++;result[count] = (int*)malloc(2 * sizeof(int));result[count][0] = intervals[i][0];result[count][1] = intervals[i][1];(*returnColumnSizes)[count] = 2;}}// 更新返回的结果大小*returnSize = count + 1;return result;
}// 测试代码
int main() {int intervalsArray[4][2] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};int intervalsSize = 4;int* intervals[4];for (int i = 0; i < intervalsSize; i++) {intervals[i] = intervalsArray[i];}int intervalsColSize[] = {2, 2, 2, 2};int returnSize;int* returnColumnSizes;int** result = merge(intervals, intervalsSize, intervalsColSize, &returnSize, &returnColumnSizes);printf("合并后的区间:\n");for (int i = 0; i < returnSize; i++) {printf("[%d, %d]\n", result[i][0], result[i][1]);free(result[i]);}free(result);free(returnColumnSizes);return 0;
}

代码逐步解析

1. 排序函数
int compare(const void* a, const void* b) {int* intervalA = *(int**)a;int* intervalB = *(int**)b;if (intervalA[0] != intervalB[0]) {return intervalA[0] - intervalB[0];}return intervalA[1] - intervalB[1];
}
  • 使用 qsort 函数按区间起点排序。
  • 如果起点相同,按终点排序,保证区间的顺序性。

2. 初始化结果数组
int** result = (int**)malloc(intervalsSize * sizeof(int*));
*returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));
  • 动态分配 result 数组用于存储合并后的区间。
  • returnColumnSizes 存储每个区间的列数(固定为 2)。

3. 遍历合并区间
if (intervals[i][0] <= result[count][1]) {result[count][1] = (intervals[i][1] > result[count][1]) ? intervals[i][1] : result[count][1];
} else {count++;result[count] = (int*)malloc(2 * sizeof(int));result[count][0] = intervals[i][0];result[count][1] = intervals[i][1];(*returnColumnSizes)[count] = 2;
}
  • 如果当前区间起点 intervals[i][0] 小于等于结果数组最后一个区间的终点 result[count][1],说明有重叠,更新终点。
  • 如果没有重叠,将当前区间作为一个新区间加入结果数组。

4. 返回结果
*returnSize = count + 1;
  • 返回合并后的区间数量。

测试用例

输入:
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
执行过程:
  1. 按起点排序:[[1, 3], [2, 6], [8, 10], [15, 18]]
  2. 遍历合并:
    • 区间 [1, 3][2, 6] 有重叠,合并为 [1, 6]
    • 区间 [8, 10] 无重叠,加入结果。
    • 区间 [15, 18] 无重叠,加入结果。
输出:
result = [[1, 6], [8, 10], [15, 18]]

复杂度分析

  1. 时间复杂度

    • 排序:O(n log n)n 为区间数量。
    • 遍历合并:O(n)
    • 总时间复杂度:O(n log n)
  2. 空间复杂度

    • 排序额外空间:O(log n)(取决于排序算法实现)。
    • 结果数组:O(n)
    • 总空间复杂度:O(n)

http://www.ppmy.cn/embedded/139065.html

相关文章

ML 系列: 第 23 节 — 离散概率分布 (多项式分布)

目录 一、说明 二、多项式分布公式 2.1 多项式分布的解释 2.2 示例 2.3 特殊情况&#xff1a;二项分布 2.4 期望值 &#xff08;Mean&#xff09; 2.5 方差 三、总结 3.1 python示例 一、说明 伯努利分布对这样一种情况进行建模&#xff1a;随机变量可以采用两个可能的值&#…

【Java Web】Ajax 介绍及 jQuery 实现

文章目录 AJAX介绍XMLHttpRequestjQuery实现Ajax$.ajax()$().load()$.get()$.post() AJAX介绍 AJAX&#xff08;Asynchronous JavaScript and XML&#xff09;是一种创建高效、动态网页应用的网页开发技术。它允许在不重新加载整个页面的情况下进行异步数据更新和交互&#xf…

torch.utils.data.dataset 的数据组织形式——python list、dict、tuple内存消耗量

在Pytorch中&#xff0c;我们需要通过torch.utils.data.dataset来实现数据的读取。torch.utils.data.dataset是一种非流式的数据读取策略&#xff0c;需要将数据一次性导入至内存中.如果数据规模过大&#xff0c;可能存在内存不够的问题。 import torch from torch.utils.data…

Spark使用过程中的 15 个常见问题、详细解决方案

目录 问题 1&#xff1a;Spark 作业超时问题描述解决方案Python 实现 问题 2&#xff1a;内存溢出问题描述解决方案Python 实现 问题 3&#xff1a;Shuffle 性能问题问题描述解决方案Python 实现 问题 4&#xff1a;Spark 作业调度不均问题描述解决方案Python 实现 问题 5&…

美创科技膺选CNVD技术组支撑单位!

国家信息安全漏洞共享平台&#xff08;CNVD&#xff09;发布安全公告&#xff08;编号&#xff1a;CNTA-2024-0019&#xff09;&#xff0c;宣布新增八家支撑单位。美创科技凭借数据安全领域的技术实力和专业服务能力&#xff0c;顺利通过支撑能力候选考察&#xff0c;首次获得…

SQL 语句优化及编程方法

DBMS生成的执行计划在很大程度上要受到代码外部结构的影响。因此要想优化查询性能&#xff0c;就必须要知道如何写代码才能使优化器的执行效率更高。 但是&#xff0c;不能为了“效率”牺牲代码的可读性&#xff0c;要让代码清晰。 1 查询优化 在解决SQL造成的性能问题时&am…

Redis面试篇笔记(持续更新)

一、redis主从集群 单节点redis的并发能力是由上限的&#xff0c;要进一步提高redis的并发能力可以搭建主从集群&#xff0c;实现读写分离&#xff0c;一主多从&#xff0c;主节点写数据&#xff0c;从节点读数据 部署redis主从节点的docker-compose文件命令解析 version: &q…

基于单片机的厂房防火报警系统

本设计基于单片机的厂房防火报警系统&#xff0c;选用STC89C52RC作为核心的控制芯片&#xff0c;并且使用GSM技术来控制各种传感器&#xff0c;来实现多功能、多方面的安全监测。其中传感器主要包括&#xff1a;烟雾传感器、火焰传感器和温度传感器。主控芯片与这些传感器&…