【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。

明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。

合并区间【MID】

如果我们按照区间的左端点排序那么在排完序的列表中可以合并的区间一定是连续的。

如下图所示标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间它们在排完序的列表中是连续的

我们用数组

首先我们将列表中的区间按照左端点升序排序。

然后我们将第一个区间加入

merged

数组中并按顺序依次考虑之后的每个区间如果当前区间的左端点在数组

merged

中最后一个区间的右端点之后那么它们不会重合我们可以直接将这个区间加入数组

merged

总体思路是左端点从小到大排列每次比较只要比较新区间的左端点是否在已合并区间右端点之后就可以了在之后则独立在之前则重叠而且由于左端点升序在之前也是在之前已合并区间的中间极端情况是和已排序区间左端点重叠

代码实现

代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可***

param

先对集合进行排序intervals.sort(Comparator.comparingInt(interval

interval.start));//

如果结果区间为空或者当前区间左端点大于已合并区间右端点则当前区间作为独立子区间加入集合if

(result.size()

否则认为当前区间与已合并区间有重叠只需更新合并区间右端点result.get(result.size()

1).end

Math.max(result.get(result.size()

1).end,

代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可***

param

Comparator.comparingInt(interval-interval[0]));//

遍历已排序数组进行区间合并int[][]

如果已合并区间为空或当前区间左端点大于已合并区间右端点则不重叠if

(idx

反之则重叠已两个区间较大值为新的右边界result[idx][1]

rightPoint);}}return

合并区间是一个常见的算法问题通常用于合并具有重叠部分的区间以简化问题或提供更清晰的表示。

以下是关于合并区间问题的时间复杂度和空间复杂度的讨论

时间复杂度

时间复杂度是衡量算法性能的关键指标它表示算法在输入规模增加时所需的运行时间。

对于合并区间问题一种常见的解决方法是首先将区间按照起始值进行排序然后遍历这些区间并合并它们。

O(n*log(n))

遍历和合并一旦区间排序完成遍历区间并合并重叠的部分通常需要线性时间即

O(n*log(n))其中

空间复杂度表示算法在执行过程中所需的额外内存空间。

对于合并区间问题空间复杂度通常取决于存储合并后的区间的数据结构。

如果您在原始区间上就地修改而不创建额外的数据结构则空间复杂度是

如果您创建一个新的数据结构来存储合并后的区间空间复杂度将取决于这个数据结构的大小。

通常情况下合并后的区间数目会少于或等于初始区间数目因此空间复杂度也是

O(1)

大于原始数组的长度新数组将在末尾用默认值填充这个默认值取决于元素的数据类型例如数值类型默认是0引用类型默认是null。

这个方法允许你在不改变原始数组的情况下创建一个具有不同长度的新数组非常方便特别是在需要调整数组大小时。

例如

int[]

Comparator.comparingInt(interval-interval[0]))

Java

进行排序。

排序是基于二维数组中每个子数组的第一个元素interval[0]的值来进行的也就是按照子数组的起始值进行排序。

intervals

Comparator.comparingInt(interval

interval[0])

是一个比较器它告诉排序方法要按照每个子数组的第一个元素interval[0]的值进行升序排序。

intervals

中每个子数组的第一个元素起始值来对二维数组进行排序从小到大排列。

排序后intervals

这对于处理区间的问题非常有用因为它可以将区间按照起始值进行排序使得你可以更轻松地执行各种区间操作比如合并重叠区间或查找包含某个点的区间等操作。