目錄
題目：
示例：
分析：
代碼：
題目：
示例：
分析：
和昨天的題大差不差，我們?nèi)匀皇怯幸欢褏^(qū)間，題目給我們一個新的區(qū)間，要我們把新區(qū)間插入到原本的區(qū)間數(shù)組里，并且能合并的要合并。
我們可以直接把新區(qū)間放入數(shù)組里，接著執(zhí)行昨天的代碼即可，一行都不用改，甚至形參名字都是一樣的。文章來源：http://www.zghlxwxcb.cn/news/detail-684635.html
由于本題中原始數(shù)組就是按照左區(qū)間升序排序，因此我們可以做一個小優(yōu)化，我們按照左區(qū)間升序的這樣一個規(guī)則插入新區(qū)間，這樣就不必再對數(shù)組進行排序從而減少運行時間了。我們只需要找到原始區(qū)間中第一個左區(qū)間大于新區(qū)間的左區(qū)間的區(qū)間即可，然后將新區(qū)間插入到這個區(qū)間的前面，接著再按照昨天的代碼。文章來源地址http://www.zghlxwxcb.cn/news/detail-684635.html
代碼：
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
//昨天的代碼照搬
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int>b){return a[0]<b[0];});
vector<vector<int>>res;
int begin=intervals[0][0],end=intervals[0][1]; //臨時變量記錄左右區(qū)間,初始化為數(shù)組第一個元素
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]>end){ //如果新區(qū)間的左區(qū)間大于臨時的右區(qū)間,則發(fā)生區(qū)間不重合
res.push_back({begin,end}); //添加臨時變量的區(qū)間
begin=intervals[i][0],end=intervals[i][1]; //更新兩個臨時變量
}else{
end=max(end,intervals[i][1]); //如果區(qū)間重合,那么更新臨時變量的右區(qū)間為較大值
}
}
res.push_back({begin,end});
return res;
//小小優(yōu)化一下
int index=0;
for(;index<intervals.size();index++){
if(newInterval[0]<=intervals[index][0]) break;
}
intervals.insert(intervals.begin()+index,newInterval);
vector<vector<int>>res;
int begin=intervals[0][0],end=intervals[0][1]; //臨時變量記錄左右區(qū)間,初始化為數(shù)組第一個元素
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]>end){ //如果新區(qū)間的左區(qū)間大于臨時的右區(qū)間,則發(fā)生區(qū)間不重合
res.push_back({begin,end}); //添加臨時變量的區(qū)間
begin=intervals[i][0],end=intervals[i][1]; //更新兩個臨時變量
}else{
end=max(end,intervals[i][1]); //如果區(qū)間重合,那么更新臨時變量的右區(qū)間為較大值
}
}
res.push_back({begin,end});
return res;
}
};到了這里，關(guān)于【力扣每日一題】2023.8.28 插入?yún)^(qū)間的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
