力扣第 56 题 合并区间

解法思路

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)。

原文地址：https://blog.csdn.net/weixin_48941116/article/details/143844841

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！