网站建设销售人员培训教程,wordpress+typecho,哈尔滨网站建设步骤,wap是什么意思啊文章目录 Tag题目解读题目来源解题思路方法一#xff1a;合并区间方法二#xff1a;模拟 其他语言python3 写在最后 Tag
【模拟】【数组】 题目解读
给定一个含有多个无重叠区间的数组#xff0c;并且数组已经按照区间开始值升序排序。在列表中插入一个新的区间#xff0… 文章目录 Tag题目解读题目来源解题思路方法一合并区间方法二模拟 其他语言python3 写在最后 Tag
【模拟】【数组】 题目解读
给定一个含有多个无重叠区间的数组并且数组已经按照区间开始值升序排序。在列表中插入一个新的区间你需要确保列表中的区间仍然有序且不重叠如果有必要的话可以合并区间。 题目来源
57. 插入区间 解题思路
数据量为 1 0 4 10^4 104基本上需要时间复杂度为 O ( n ) O(n) O(n) 或者 O ( n l o g n ) O(nlogn) O(nlogn)的解题方法。
方法一合并区间
将 newInterval 区间加入到数组 intervals 数组中再对数组排序接下来按照 228汇总区间进行解决。
实现代码 复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) n n n 为新的数组intervals长度。
空间复杂度为 O ( 1 ) O(1) O(1)。
方法二模拟
第二种方法就是模拟遍历 intervals找到与 newInterval 区间重合的区间合并重合的区间。需要注意边界的处理
具体地记当我们遍历到区间为 [ l i , r i ] [l_i, r_i] [li,ri]区间 newInterval 的左右端点分别为 l e f t left left 和 r i g h t right right
如果 r i l e f t r_i left rileft说明 [ l i , r i ] [l_i, r_i] [li,ri] 与新区间不重合并且位于新区间的左侧此时可以直接将区间 [ l i , r i ] [l_i, r_i] [li,ri] 加入答案数组中如果 l i r i g h t l_i right liright说明 [ l i , r i ] [l_i, r_i] [li,ri] 与新区间不重合并且位于新区间的左侧此时可以直接将区间 [ l i , r i ] [l_i, r_i] [li,ri] 加入答案数组中其他情况下说明当前遍历的区间与新区间重合我们需要进行合并操作两个区间的合并也就是求交集操作即两个区间左端点的最小值作为合并后区间的左端点两个区间右端点的最大值作为合并后区间的右端点。
还有一种情况新的区间在区间数组中第一个区间的左侧或者位于最后一个区间的右侧这时候我们可以在遍历区间数组的时候一并解决。
具体地需要维护一个 bool 变量 isPlaced 表示需要合并的新数组是否已经放置在了合适的位置该变量初始化为 false。在遍历数组区间的时候如果新区间位于当前遍历的区间左侧即 l i r i g h t l_i right liright 的情况
且 isPlaced false则将新区间加入到答案数组中将当前遍历的区间加入到答案数组中。
如果遍历完毕区间数组isPlaced false说明新区间位于区间数组最后一个区间的右侧则直接将新区间加入到答案数组中。
实现代码
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {vectorvectorint res;int l newInterval[0];int r newInterval[1];bool isPlaced false; // 新的区间是否已经安置好for (auto inter : intervals) {if (inter[0] r) {if (!isPlaced) {isPlaced true;res.push_back({l, r});}res.push_back(inter);}else if (inter[1] l) {res.push_back(inter);}else {l min(inter[0], l);r max(inter[1], r);}}if (!isPlaced) {res.push_back({l, r});}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组intervals的长度。
空间复杂度为 O ( 1 ) O(1) O(1)。 其他语言
方法一的其他语言已经在 【面试经典150 | 区间】合并区间 介绍过了这里只贴出方法二的其他程序语言的解法。
python3
class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) - List[List[int]]:left, right newIntervalisPlaced Falseres []for li, ri in intervals:if li right:if not isPlaced:res.append([left, right])isPlaced Trueres.append([li, ri])elif ri left:res.append([li, ri])else:left min(left, li)right max(right, ri)if not isPlaced:res.append([left, right])return res写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
