力扣最热100题——56.合并区间

时间：2024-03-13 21:38:04

吾日三省吾身

还记得梦想吗

正在努力实现它吗

可以坚持下去吗

目录

吾日三省吾身

力扣题号：56. 合并区间 - 力扣（LeetCode）

题目描述

Java解法一：排序然后原地操作

具体代码如下

Java解法二：new一个list，然后两端操作

具体代码如下

解法一的C++版本

总结

 

力扣题号：56. 合并区间 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

        以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

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

Java解法一：排序然后原地操作

  1. 特殊情况处理： 首先，检查输入的区间数组是否为空或只包含一个区间。如果是这种情况，直接返回原始的区间数组，因为不需要合并。

  2. 排序： 使用 Arrays.sort 方法对区间数组进行排序。排序的依据是区间的起始位置（o1[0] - o2[0]），这确保了数组按照起始位置升序排列。

  3. 合并重叠区间： 遍历排序后的区间数组。对于每一对相邻的区间，检查它们是否有重叠。如果存在重叠，将两个区间合并成一个，并用合并后的区间替代原来的两个区间。这一过程使用一个循环和条件语句来判断是否有重叠。

  4. 转换为数组： 使用 list.size() 创建一个相应长度的二维数组，并将 List 中的元素复制到该数组中。最后返回这个二维数组作为结果

具体代码如下
class Solution {
    public int[][] merge(int[][] intervals) {

        int length = intervals.length;
        // 0 个和一个都不用比了，直接返回
        if (length <= 1) {
            return intervals;
        }

        // 利用比较器来先排个序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 定义一个list，这样长度才是动态的

        List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
        
        
        for (int i = 0; i < list.size() - 1; i++) {
            // 获取第一个数组
            int[] arr1 = list.get(i);
            int start1 = arr1[0];
            int end1 = arr1[1];
            // 获取第二个数组
            int[] arr2 = list.get(i + 1);
            int start2 = arr2[0];
            int end2 = arr2[1];

            // 判断是否有重合
            if (end1 >= start2) {
                // 有重合，得到并集
                // [2,3],[4,5],[6,7],[8,9],[1,10]
                int[] bing = {Math.min(start1, start2), Math.max(end1, end2)};
                list.remove(i);
                list.set(i, bing);
                i--;
            }
        }

        int[][] res = new int[list.size()][];
        // 转化为int[][]
        int i = 0;
        for (int[] ints : list) {
            res[i++] = ints;
        }
        
        return res;
    }
}

虽然说不是很快，你就说好不好理解吧  (`へ´*)ノ

Java解法二：new一个list，然后两端操作

具体代码如下

下面是力扣的代码

  1. 特殊情况处理： 首先检查输入的区间数组是否为空。如果为空，直接返回一个空的二维数组 new int[0][2] 表示无合并区间。

  2. 排序： 使用 Arrays.sort 方法对区间数组进行排序，排序的依据是区间的起始位置，即 interval1[0] - interval2[0]。

  3. 遍历合并： 遍历排序后的区间数组。对于每个区间，检查是否与之前的合并结果有重叠。如果没有重叠，直接将当前区间加入合并结果列表中。如果有重叠，更新合并结果列表的最后一个区间的结束位置，确保合并后的区间仍然是不重叠的。

  4. 转换为数组： 将最终的合并结果列表转换为二维数组，并返回作为结果。

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

算你巧妙，但是我的还是更好理解一点(*^▽^*)

但是你小子也没快多少嘛  ╭(╯^╰)╮

解法一的C++版本

class Solution {
public:
    std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
        int length = intervals.size();
        
        // 0 个和一个都不用比了，直接返回
        if (length <= 1) {
            return intervals;
        }

        // 利用比较器来先排个序
        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[0] < b[0];
        });

        // 定义一个vector，这样长度才是动态的
        std::vector<std::vector<int>> result(intervals);
        
        for (int i = 0; i < result.size() - 1; i++) {
            // 获取第一个数组
            std::vector<int>& arr1 = result[i];
            int start1 = arr1[0];
            int end1 = arr1[1];
            // 获取第二个数组
            std::vector<int>& arr2 = result[i + 1];
            int start2 = arr2[0];
            int end2 = arr2[1];

            // 判断是否有重合
            if (end1 >= start2) {
                // 有重合，得到并集
                // [2,3],[4,5],[6,7],[8,9],[1,10]
                std::vector<int> bing = {std::min(start1, start2), std::max(end1, end2)};
                result.erase(result.begin() + i);
                result[i] = bing;
                i--;
            }
        }

        return result;
    }
};

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

虽然慢的无语，但你就说过没过吧。。。。 (￣ε(#￣)☆╰╮(￣▽￣///)

总结

挑战力扣失败，o(╥﹏╥)o

被制裁了

相关文章