[LeetCode 笔记] 56. Merge Intervals

前言

　　这题运用双指针来实作，目标是把阵列中的元素重叠的部分合併起来，有使用到合併和排序的演算法，时间複杂度估为 O(n log n)，这里有 JAVA 和 Python 的写法。

题目

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

给定一个阵列 intervals 其中，间隔在 intervals[i] = [starti, endi]，合併全部有重叠的间隔，并回传覆盖输入中所有区间的非重叠区间的阵列。

题目连结：https://leetcode.com/problems/merge-intervals/

题目限制

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

範例

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]Output: [[1,6],[8,10],[15,18]]Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

区间 [ 1, 3 ] 和 [ 2, 6 ] 重叠，将它们合併为 [ 1, 6 ]

Input: intervals = [[1,4],[4,5]]Output: [[1,5]]Explanation: Intervals [1,4] and [4,5] are considered overlapping.

区间 [ 1, 4 ] 和 [ 4, 5 ] 可被视为重叠区间

思路&笔记

将原始的阵列做升序排序宣告一个 res (来装判断过的元素)把 intervals 的第一个元素装入 resfor 迴圈从 intervals 第二个元素开始循环如果 res 最后一个元素后面的值 ≥ intervals 第二个元素前面的值的话将 intervals 第二个元素后面的值比较 res 最后一个元素后面的值，取较大的值合併

JAVA 实现

class Solution {    public int[][] merge(int[][] intervals) {        if (intervals == null || intervals.length == 0) {            return intervals;        };        List<int[]> res = new ArrayList<>(); // 初始化阵列 (因为不知道阵列元素有几个)        Arrays.sort(intervals, (a, b) -> (a[0] - b[0])); // 把阵列排成升序        res.add(intervals[0]); // 添加阵列第一个区间 res = [[1,3]]        // 原本的阵列从第二个开始循环比较        for (int i = 1; intervals.lenght - 1; i++) {            // 如果有重叠的话            if (res.get(res.size() - 1)[1] >= intervals[i][0]) {                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], intervals[i][1]); // 取较大的值合併            } else {                res.add(intervals[i]); // 没有重叠，直接加入结果列表            }        }        return return res.toArray(new int[res.size()][]); // 没有重叠，转成阵列输出    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def merge(self, intervals: List[List[int]]) -> List[List[int]]:        intervals.sort()  # 对区间列表进行排序        # 準备一个容器来装合併的元素 (索引 0 先放进去)        res = [intervals[0]]  # 添加阵列第一个区间 res = [[1,3]]        # 原本的阵列从第二个开始循环比较        # intervals[1:]        # Iteration 1: start = 2, end = 6        # Iteration 2: start = 8, end = 10        # Iteration 3: start = 15, end = 18        for start, end in intervals[1:]:            # 如果有重叠            if res[-1][1] >= start:                res[-1][1] = max(res[-1][1], end)  # 取较大的值合併            else:                res.append([start, end])  # 没有重叠，直接加入结果列表        return res

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/08/27/LeetCode-56-Merge-Intervals-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论