(LeetCode 面试经典 150 题) 57. 插入区间 (数组)

题目：57. 插入区间

思路：数组，时间复杂度0(n)。

先将newInterval左侧的区间都添加到v中，然后处理重复的区间，最后再将右侧的区间都加到v中即可。细节看注释。

C++版本：

class Solution {public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { // 答案 vector<vector<int>> v; // intervals为空时，直接返回newInterval即可 if(intervals.size()==0){ v.push_back(newInterval); return v; } // 先将newInterval左侧的区间都添加到v中 int l=newInterval[0],r=newInterval[1]; int i; for(i=0;i<intervals.size();i++){ if(l>intervals[i][1]){ v.push_back(intervals[i]); }else{ break; } } // 然后处理重复的区间 if(i<intervals.size())l=min(intervals[i][0],l); for(;i<intervals.size();i++){ if(r>=intervals[i][0]){ r=max(r,intervals[i][1]); }else{ break; } } v.push_back({l,r}); // 最后再将右侧的区间都加到v中 for(;i<intervals.size();i++){ v.push_back(intervals[i]); } return v; }};

JAVA版本：

class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> v=new ArrayList<>(); if(intervals.length==0){ v.add(newInterval); return v.toArray(new int[v.size()][]); } int l=newInterval[0],r=newInterval[1]; int i; for(i=0;i<intervals.length;i++){ if(l>intervals[i][1]){ v.add(intervals[i]); }else{ break; } } if(i<intervals.length)l=Math.min(intervals[i][0],l); for(;i<intervals.length;i++){ if(r>=intervals[i][0]){ r=Math.max(r,intervals[i][1]); }else{ break; } } v.add(new int[]{l,r}); for(;i<intervals.length;i++){ v.add(intervals[i]); } return v.toArray(new int[v.size()][]); }}

GO版本：

func insert(intervals [][]int, newInterval []int) [][]int { v:=[][]int{} if len(intervals)==0 { v=append(v,newInterval) return v } l,r:=newInterval[0],newInterval[1] i:=0 for ;i<len(intervals);i++ { if l>intervals[i][1] { v=append(v,intervals[i]) }else{ break } } if i<len(intervals) { l=min(l,intervals[i][0]) } for ;i<len(intervals);i++ { if r>=intervals[i][0] { r=max(r,intervals[i][1]) }else{ break } } v=append(v,[]int{l,r}) for ;i<len(intervals);i++ { v=append(v,intervals[i]) } return v}