56. Merge Intervals.jpg

LeetCode 56. Merge Intervals

Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

描述

給定間隔的集合，合并所有重疊的間隔。

思路

• 這道題是給定一些區(qū)間，要求合并有重疊部分的區(qū)間.
• 思路很清晰，我們首先按照區(qū)間的起始位置，對所有的區(qū)間從小到大排序.
• 然后我們檢查每一個區(qū)間的起始位置是否在前一個區(qū)間之內(nèi)，如果是，并且此區(qū)間的結(jié)束位置大于上一個區(qū)間的結(jié)束位置，我們我們更新上一個區(qū)間的結(jié)束位置
• 如果不是，我們把當前區(qū)間添加到結(jié)果數(shù)組中.
• 這里說一下排序.

快速排序

• 這道題我們采用快速排序.
• 快排的思路是在數(shù)組中隨便找一個值P，然后把數(shù)組分成兩部分：左邊部分的所有值小于等于P，右邊的所有值大于等于P（以從小到大排序為例）.
• 快排是不穩(wěn)定的排序算法，平均時間復雜的O（nlogn）,空間復雜度O(1).
• 說一下空間復雜度：空間復雜的為常數(shù)，即要求排序在原地排序.
• 排序的關(guān)鍵是分區(qū)：假設(shè)有一個數(shù)組A[0:max],我們?nèi)∽詈笠粋€值P=A[max]為分區(qū)點，我們假設(shè)A[0:i-1]為已經(jīng)排好序的區(qū)間，我們每次從未排序區(qū)間中找小于等于P的值
• 然后我們把這個值放到已排序區(qū)間的尾部，i自增一次，然后一直重復，直到末尾，最后把A[i]和A[max]交換，就完了成了分區(qū).

class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution:
    def depart(self, intervals, left, right):
        # 確定分區(qū)點的位置
        pivot = left+((right-left) >> 1)
        # 將分區(qū)點和最后一個位置交換
        intervals[right], intervals[pivot] = intervals[pivot], intervals[right]
        # i，j 初始位置為最左邊的位置，i表示以排序區(qū)間的末尾（不包含在排序區(qū)間之內(nèi)）
        i, j = left, left
        for j in range(left, right):
            # 如果當前位置比pivot位置的值小（由于已經(jīng)把pivot交換到最后一個位置，pivot==riht）
            if intervals[j].start < intervals[right].start:
                # 把當前位置的值放入已排序區(qū)間的末尾
                intervals[i], intervals[j] = intervals[j], intervals[i]
                # 已排序區(qū)間自增一次
                i += 1
        # 把最后一個位置和i交換
        intervals[i], intervals[right] = intervals[right], intervals[i]
        return i

    def quicksort(self, intervals, left, right):
        # 遞歸結(jié)束條件，當left>=right時
        if left >= right:
            return
        # 對數(shù)組取某一個值，分為兩塊
        middle = self.depart(intervals, left, right)
        # 對左邊排序
        self.quicksort(intervals, left, middle-1)
        # 對右邊排序
        self.quicksort(intervals, middle+1, right)

    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        ans = []
        # 對
        self.quicksort(intervals, 0, len(intervals)-1)
        # 這里也可以用python自帶的排序函數(shù)，python排序函數(shù)是用C實現(xiàn)的，速度更快
        # intervals = sorted(intervals, key=lambda x: x.start)
        for item in intervals:
            if not ans or item.start > ans[-1].end:
                ans.append(item)
            elif item.end > ans[-1].end:
                ans[-1].end = item.end
        return ans

源代碼文件在這里.
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源，作者信息和本聲明.