网站建设的方法有哪些方面,自己做网站兼职,云南网站开发,小米发布会图文57. 插入区间
插入区间 给你一个无重叠的 #xff0c;按照区间起始端点排序的区间列表。 在列表中插入一个新的区间#xff0c;你需要确保列表中的区间仍然有序且不重叠#xff08;如果有必要的话#xff0c;可以合并区间#xff09;。
示例 1#xff1a;
输入#x…57. 插入区间
插入区间 给你一个无重叠的 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间你需要确保列表中的区间仍然有序且不重叠如果有必要的话可以合并区间。
示例 1
输入intervals [[1,3],[6,9]], newInterval [2,5] 输出[[1,5],[6,9]]
示例 2
输入intervals [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval [4,8] 输出[[1,2],[3,10],[12,16]] 解释这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3
输入intervals [], newInterval [5,7] 输出[[5,7]]
示例 4
输入intervals [[1,5]], newInterval [2,3] 输出[[1,5]]
示例 5
输入intervals [[1,5]], newInterval [2,7] 输出[[1,7]]
提示
0 intervals.length 104 intervals[i].length 2 0 intervals[i][0] intervals[i][1] 105 intervals 根据 intervals[i][0] 按 升序 排列 newInterval.length 2 0 newInterval[0] newInterval[1] 105
思路
最开始的思路就是先把新的区间按照起点的顺序插入到旧区间内之后对所有区间进行判断来将可以合并的区间合并起来。但是如果直接这样做的话因为插入的时候需要将所有元素后移一位而对于区间合并每次合并后都需要删除一个元素导致每次需要将所有元素前移一位这样的在后面测试案例较大的时候是没法通过的。因此需要别的思路来解决这几个问题。 除此之外还需要知道有两个区间(a,b),(c,d),当发现cb的时候说明两个区间需要合并。并且合并后的区间是(a,max(b,d))。
解题方法
创建一个ans来保存最后的区间列表第一步将新的区间插入到旧区间内这里采用遍历旧区间intervals通过判断newInterval的起点大小把小于newInterval起点的区间放进ans中当发现不满足的时候就是该放入newInterval的位置了这个时候就可以把newInterval加入ans中。这样就做到了将newInterval插入到旧区间内。 第二步进行判断新插入的区间newInterval是否需要合并与ans中最后一个区间进行判断此时newInterval还没有插入ans中如果需要合并那么直接合并就行了也就不需要newInterval插入了。 第三步在把新的区间newInterval放入包括合并后就需要把intervals剩下的区间加入ans中了不过在加入的时候需要进行判断如果需要合并那么直接合并。如果不需要合并只需要加入剩下的区间了。 第四步在第三步之前考虑了一个特殊情况也就是新区间是是放入最后一个位置这个时候需要单独把newInterval放入ans后并且判断是否需要合并。
复杂度
时间复杂度: O(n)
空间复杂度: O(n)
Code
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {vectorvectorint ans;if(intervals.size()0){intervals.push_back(newInterval);return intervals;}int i0,k0;//找到新区间应该放置在旧区间的位置for(;iintervals.size();i){if(newInterval[0]intervals[i][0]){if(i0newInterval[0]intervals[i-1][1]){ans[i-1][1]max(ans[i-1][1],newInterval[1]);ki-1;}else{ki;ans.push_back(newInterval);}break;}ans.push_back(intervals[i]);}//如果新的区间放在最后一个位置if(iintervals.size()){if(newInterval[0]intervals[i-1][1]){ans[i-1][1]max(ans[i-1][1],newInterval[1]);}else{ans.push_back(newInterval);}}//新的区间放在了旧区间中for(;iintervals.size();i){if(ans[k][1]intervals[i][0]){ans[k][1]max(ans[k][1],intervals[i][1]);}else{ans.push_back(intervals[i]);}}return ans;}
};
