56. 合并区间(Merge Intervals)

56. 合并区间(Merge Intervals)

题解 排序+一次扫描
  1. 特判,若 i n t e r v a l s intervals intervals为空,返回 [ ] [] []
  2. 定义数组长度 n n n,当前合并区间 [ l e f t , r i g h t ] [left,right] [left,right],初始化: l e f t = i n t e r v a l s [ 0 ] [ 0 ] , r i g h t = i n t e r v a l s [ 0 ] [ 1 ] left=intervals[0][0],right=intervals[0][1] left=intervals[0][0],right=intervals[0][1]
  3. i n t e r v a l s intervals intervals,按照左界进行排序。
  4. 从第二个区间开始遍历:
    • 若下一区间 i n t e r v a l s [ i ] intervals[i] intervals[i]的左界小于等于当前合并区间的右界,即 i n t e r v a l s [ i ] [ 0 ] = r i g h t intervals[i][0]=right intervals[i][0]=right,表示有公共部分:
      • 此时,若满足 i n t e r v a l s [ i ] intervals[i] intervals[i]的右界大于当前合并区间的右界,即 i n t e r v a l s [ i ] [ 1 ] r i g h t intervals[i][1]right intervals[i][1]right,表示 i n t e r v a l s [ i ] intervals[i] intervals[i]不包含于当前合并区间,需要更新当前合并区间的右界 r i g h t = i n t e r v a l s [ i ] [ 1 ] right=intervals[i][1] right=intervals[i][1]
    • 若下一区间 i n t e r v a l s [ i ] intervals[i] intervals[i]的左界大于当前合并区间的右界,说明没有交集
      • 将当前合并区间 [ l e f t , r i g h t ] [left,right] [left,right]加入 r e s res res
      • 更新当前合并区间左界和右界,指向下一区间,即 l e f t = i n t e r v a l s [ i ] [ 0 ] , r i g h t = i n t e r v a l s [ i ] [ 1 ] left=intervals[i][0],right=intervals[i][1] left=intervals[i][0],right=intervals[i][1]
  5. 将最后一个合并区间加入 r e s res res
  6. 返回 r e s res res
复杂度分析
  • 时间复杂度: O ( N log ⁡ N ) O(N \log N) O(NlogN),数组排序 O ( N log ⁡ N ) O(N \log N) O(NlogN),遍历数组 O ( n ) O\left(n\right) O(n),总体 O ( N log ⁡ N ) + O ( n ) O(N \log N)+O\left(n\right) O(NlogN)+O(n) O ( N log ⁡ N ) O(N \log N) O(NlogN)
  • 空间复杂度: O ( N ) O(N) O(N),借助 r e s res res保存结果
Python
class Solution:
    def merge(self, intervals: List[List[int]]) - List[List[int]]:
        if(not intervals):
            return []
        n=len(intervals)
        intervals.sort()
        res=[]
        left=intervals[0][0]
        right=intervals[0][1]
        for i in range(1,n):
            if(intervals[i][0]=right):
                if(intervals[i][1]right):
                    right=intervals[i][1]
            else:
                res.append([left,right])
                left=intervals[i][0]
                right=intervals[i][1]
        res.append([left,right])
        return res
另一种写法
class Solution:
    def merge(self, intervals: List[List[int]]) - List[List[int]]:
        intervals=sorted(intervals)
        res=[]
        n=len(intervals)
        i=0
        while(in):
            left=intervals[i][0]
            right=intervals[i][1]
            while(in-1 and intervals[i+1][0]=right):
                i+=1
                right=max(intervals[i][1],right)
            res.append([left,right])
            i+=1
        return res
Java(待完成)
最新回复(0)
/jishuxX9yQaC4i6rTOZPN_2F67McpjCTrMxyvnpA8yU8g_3D_3D4858760
8 简首页