网站是如何设计配置方案的,wordpress搜索功能优化,东莞哪里有网页设计,乌海网站建设公司文章目录 1.问题描述2.难度等级3.热门指数4.解题思路参考文献 1.问题描述
以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间#xff0c;并返回 一个不重叠的区间数组#xff0c;该数组需恰好覆盖输… 文章目录 1.问题描述2.难度等级3.热门指数4.解题思路参考文献 1.问题描述
以数组 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 1042.难度等级
Medium。
3.热门指数
★★★★☆
4.解题思路
如果我们按照区间的左端点排序那么在排完序的列表中可以合并的区间一定是连续的。如下图所示标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间它们在排完序的列表中是连续的 我们用数组 merged 存储最终的答案。
首先我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中并按顺序依次考虑之后的每个区间 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后那么它们不会重合我们可以直接将这个区间加入数组 merged 的末尾 否则它们重合我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点将其置为二者的较大值。
时间复杂度
O(nlogn)其中 n 为区间的数量。除去排序的开销我们只需要一次线性扫描所以主要的时间开销是排序的 O(nlogn)。
空间复杂度
O(1)不包括存储答案的空间使用常数空间。
下面以 Golang 为例给出实现。
func merge(intervals [][]int) [][]int {slices.SortFunc(intervals, func(a, b []int) int {return cmp.Compare(a[0], b[0])})var merged [][]intfor _, v : range intervals {if merged nil {merged append(merged, v)continue}tail : merged[len(merged)-1]// 不重合if v[0] tail[1] {merged append(merged, v)} else {// 重合选择较大的右端点。if v[1] tail[1] {tail[1] v[1]}}}return merged
}参考文献
56. 合并区间- LeetCode
