题目描述
给出一个区间的集合,请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
注意:输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
提示:
intervals[i][0] <= intervals[i][1]
难度:Middle
前置知识
- 排序
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
- 先对数组进行排序,排序的依据就是每一项的第一个元素的大小。
- 然后我们对数组进行遍历,遍历的时候两两运算(具体运算逻辑见下)
- 判断是否相交,如果不相交,则跳过
- 如果相交,则合并两项
关键点解析
- 对数组进行排序简化操作
- 如果不排序,需要借助一些 hack,这里不介绍了
代码
- 语言支持: Javascript,Python3
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* @lc app=leetcode id=56 lang=javascript
*
* [56] Merge Intervals
*/
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
function intersected(a, b) {
if (a[0] > b[1] || a[1] < b[0]) return false;
return true;
}
function mergeTwo(a, b) {
return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
}
var merge = function (intervals) {
// 这种算法需要先排序
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < intervals.length - 1; i++) {
const cur = intervals[i];
const next = intervals[i + 1];
if (intersected(cur, next)) {
intervals[i] = undefined;
intervals[i + 1] = mergeTwo(cur, next);
}
}
return intervals.filter((q) => q);
};
Python3 Code:
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
"""先排序,后合并"""
if len(intervals) <= 1:
return intervals
# 排序
def get_first(a_list):
return a_list[0]
intervals.sort(key=get_first)
# 合并
res = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i][0] <= res[-1][1]:
res[-1] = [res[-1][0], max(res[-1][1], intervals[i][1])]
else:
res.append(intervals[i])
return res
复杂度分析
- 时间复杂度:由于采用了排序,因此复杂度大概为 $O(NlogN)$
- 空间复杂度:$O(N)$
- 原题leetcode链接:https://leetcode-cn.com/problems/merge-intervals/
更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com