目录

第一站 LeetCode 新手村

前言

        56. 合并区间

        题目描述

        解题思路

        代码 

总结

题目来源

第一站 LeetCode 新手村

前言

最近玩OJ赛，发现对算法的理解还需要更加扎实，code能力还可以进一步提升，所以做这样一个算法的系列文章，用于记录学习心得，交流经验，更好地进步和成长。

56. 合并区间

题目描述

以数组 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 <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

解题思路

预知

LeetCode是核心代码模式，所以只需要考虑核心算法，输入由系统自动完成，最后的输出以return返回；

思路

请参考代码和注释

vector容器实现二维数组

vector<vector<int>>

这样的定义方式，相当于在vector容器中又套用了一个vector容器，以实现在容器中存储一维数组的元素，使其在存储上呈现如下效果，访问是按照索引进行遍历即可；

[[1,3],[2,6],[8,10],[15,18]]

具体遍历如下，我们引用代码中的一段作为示例进行解释

int L = intervals[i][0], R = intervals[i][1];
i代表的是外层vector 即，[ [ ], [ ],  [ ] ]的第几个元素， 0代表内层vector的第一个元素 [L, R]
i
i+1
i+2
0, 1

代码 

C++

class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0){
return {};
//{}的含义是返回一个空的vector
}
sort(intervals.begin(), intervals.end()); //这里使用sort排序，默认以每一组元素第一个值非降序排序
vector<vector<int>> merged;
//创建一个新的数组，将值存储在新的数组中，不对原数组进行修改，也符合程序编写过程中的操纵数组的要求
for(int i=0;i<intervals.size();i++){
//遍历整个数组
int L = intervals[i][0], R = intervals[i][1]; //元素的左值，元素的右值
if(!merged.size() || merged.back()[1] < L){
//当merged数组为空，或数组位发生重叠时
merged.push_back({L, R});
//把数组元素填入到merged中
}
else{
//若数组重叠
merged.back()代表二维数组中最后一个一维数组元素
merged.back()[1] = max(merged.back()[1], R); //元素右边界取最大的一个
}
}
return merged;
}
};

总结

以上就是今天要讲的内容，本文仅仅简单讲解了《56. 合并区间》这一题目，对sort排序的适用情况，二维数组的操作，和编程中尽量不改变原数组等要求有了更好的理解。

题目来源

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-intervals

最后

以上就是聪明大地为你收集整理的力扣 56. 合并区间第一站 LeetCode 新手村前言56. 合并区间总结题目来源的全部内容，希望文章能够帮你解决力扣 56. 合并区间第一站 LeetCode 新手村前言56. 合并区间总结题目来源所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。