分治算法實戰

今天我們通過 3 道 leetcode 算法題來實戰分治法。3道題的難度分別為簡單、中等和中等，各有特色。讓我們一起來領略分治的魅力吧。

1. 連續數列

首先看題目，這是 leetcode 中的面試題部分，題目內容如下：

給定一個整數數組，找出總和最大的連續數列，并返回總和。

示例：

輸入： [-2,1,-3,4,-1,2,1,-5,4]

輸出： 6

解釋： 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階：如果你已經實現復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

這個很明顯是一道動態規劃問題，而且使用動態規劃方法的時間復雜度為 $O(n)$，空間復雜度可以優化為 $O(1)$。題目描述中已經說明了可以使用分治法去求解該問題。那我們就要思考，如何分解問題，如何合并子問題的解。首先定義解決該問題的方法：

def divide(nums, left, right):
    """
    返回nums[left:right+1]總和最大的連續數列
    """
    pass

分解終止條件

當數組為空時，我們就可以停止分解了，轉而合并結果：

if left == right:
    return nums[left]

分解問題

每次將序列對半分割即可，然后使用遞歸得到子問題的解：

# 中間一分為二
mid = (left + right) // 2

# 遞歸法：得到左邊最大子序列和，不包含右邊序列
leftSum = divide(nums, left, mid)
# 遞歸得到右邊最大子序列和，不包含mid及其左邊序列
rightSum = divide(nums, mid + 1, right)

合并子問題的解

這是最關鍵的一步，上面把序列規模進行對半分割后，我們需要通過左邊序列的解和右邊序列的解一起來得出最終的完整序列的解。

假設我們定義方法： divide(nums, left, right) 為序列 nums[left:right+1] 中最大連續子列的和；

進行規模分割，有 mid=(left + right) // 2，那么原來的列表被劃分為兩個子列表：nums[left, mid+1] 和 nums[mid+1, right]。

此時 divide(nums, left, mid) 結果表示列表 nums[left:mid+1] 中的最大子序列和，記為 leftSum，而 divide(nums, mid+1, right) 的結果表示的是 nums[mid+1:right] 中的最大子序列和，記為 rightSum。

那么我們僅拿著左右著兩邊最大子序列和的最大值，即 max(leftSum, rightSum) 來作為原問題的解，是否可行？

顯然是不行的，因為如果原問題的最大連續子列并不單獨在左邊和右邊，而可能同時包含左子列和右子列的元素：

此時，我們需要考慮如何從左右子序列中找到包含左右子序列元素的最大連續子序列和。

因為序列連續，所有會比較簡單，我們直接從 mid 開始分別往左邊移動，計算包含每個元素的連續和 (該元素到 mid 位置的元素全部要包括)，找到最大值，得到 leftMidSum。

右邊的子序列做同樣的操作，得到 rightMidSum。最后這兩個值的和就是同時包含左右子序列元素的最大連續數列的和：leftMidSum + rightMidSum。

這個時候我們在拿這三個的值進行比較，找到最大值，此時得到的結果才是原問題的解：max(max(leftSum, rightSum), leftMidSum + rightMidSum)。

上述實現查找包含左右連續子序列最大和的方法如下：

# 從找出包含mid的左邊連續序列的最大值
leftVal = 0 
leftMidSum = nums[mid] - 1
for i in range(mid, left - 1, -1):
    leftVal += nums[i]
    leftMidSum = max(leftVal, leftMidSum)
    
# 找出右邊序列中最大值
rightVal = 0 
rightMidSum = nums[mid + 1] - 1
for i in range(mid + 1, right + 1):
    rightVal += nums[i]
    rightMidSum = max(rightVal, rightMidSum)

最后原問題的解為三個值中的最大值，即：

max(max(leftSum, rightSum), leftMidSum + rightMidSum)

通過上述分析，我們最終得到如下 Python 代碼：

def maxSubArray(nums):
    """
    分治法
    """   
    def divide(nums, left, right):
        if left == right:
            return nums[left]
        # 中間一分為二
        mid = (left + right) // 2
        
        # 遞歸法：得到左邊最大子序列和，不包含右邊序列
        leftSum = divide(nums, left, mid)
        # 遞歸得到右邊最大子序列和，不包含mid及其左邊序列
        rightSum = divide(nums, mid + 1, right)

        # 從找出包含mid的左邊連續序列的最大值
        leftVal = 0 
        leftMidSum = nums[mid] - 1
        for i in range(mid, left - 1, -1):
            leftVal += nums[i]
            leftMidSum = max(leftVal, leftMidSum)

        # 找出右邊序列中最大值
        rightVal = 0 
        rightMidSum = nums[mid + 1] - 1
        for i in range(mid + 1, right + 1):
            rightVal += nums[i]
            rightMidSum = max(rightVal, rightMidSum)
        # 此時leftMidSum + rightMidSum便是中間包含mid的連續子序列的最大值
        return max(max(leftSum, rightSum), leftMidSum + rightMidSum)

    return divide(nums, 0, len(nums) - 1)          

這個執行的時間復雜度為 $O(nlogn)$，提交代碼耗時在所有 Python3 提交中墊底，但是這個解題的思路卻是很重要的，鍛煉我們分治求解能力。

2. 最小 K 個數

來看一道常見的面試題，題目描述如下：

設計一個算法，找出數組中最小的k個數。以任意順序返回這k個數均可。

示例：

輸入： arr = [1,3,5,7,2,4,6,8], k = 4
輸出： [1,2,3,4]

Tips：

• 0 <= len(arr) <= 100000；

• 0 <= k <= min(100000, len(arr))；

其實不用分治法，直接考慮快排之后選擇前 k 個數即能通過題解。但是本題我們要換一種思路，使用分治法來解決該題。首先定義解決原問題的方法：

def divide(arr, left, right, k):
    """
    找出arr[left:right+1]中的最小k個數并返回    
    """
    pass

終止條件

很明顯，我們要找數組中最小的 k 個數，如果數組長度為空或者長度小于 k，我們可以直接返回該數組：

# 注意 left 和 right 用于限定數組

# 終止條件
if not k:
    return []
# 終止條件
if (right - left + 1) <= k:
    return arr[left: right + 1]

分解列表

和之前一樣，都是對半分，mid = (left + right) // 2，那么數組會被劃分為如下兩個部分：

arr[left:mid + 1] # 左半部分
arr[mid + 1:right] # 右半部分

對于的子問題的解為：

# 得到左子列的最小k個數
arr_left_k = divide(arr, left, mid, k)
# 得到右子列的最小k個數
arr_right_k = divide(arr, mid + 1, right, k)

合并子結果，得到原問題的解

首先定義方法：divide(nums, left, right, k)，該方法會找出列表 nums[left:right + 1] 中前最小的 k 個數。

我們用分治法后，將列表分成兩個子列：nums[left:mid + 1] 和 nums[mid + 1:right + 1]。這樣方法 divide(nums, left, mid, k) 返回的結果是左子列中前 k 個最小值，方法 divide(nums, mid + 1, right, k) 返回的結果是右邊子列中前 k 個最小值。

此時我們知道，整個數組的前 k 個最小值必定在這 2k 個元素中。那么接下來的問題就是從這兩 k 個值中找出最小的 k 個數即可，簡單點的方式就是快排后取前 k 個。當問題規模 n 遠大于 k 時，我們會發現排序所耗時間 $O(klogk)$ 非常小，這樣也決定了該分治算法的高效性。

# 組成2k個數的列表
arr_k = []
for i in range(len(arr_left_k)):
    arr_k.append(arr_left_k[i])
    arr_k.extend(arr_right_k)
# 使用快排方法，取前k個數，即為結果，直接返回
arr_k.sort()

最后返回我們想要的前 k 個元素即可：

return arr_k[:k]

綜合上述幾點，我們得到了如下完整的 Python 實現：

def smallestK(arr, k):
    def divide(arr, left, right, k):
        # 終止條件
        if not k:
            return []
        # 終止條件
        if (right - left + 1) <= k:
            return arr[left: right + 1]
        # 分治法
        mid = (left + right) // 2
        # 得到左子列的最小k個數
        arr_left_k = divide(arr, left, mid, k)
        # 得到右子列的最小k個數
        arr_right_k = divide(arr, mid + 1, right, k)

        # 組成2k個數的列表
        arr_k = []
        for i in range(len(arr_left_k)):
            arr_k.append(arr_left_k[i])
        arr_k.extend(arr_right_k)
        # 使用快排方法，取前k個數，即為結果，直接返回
        arr_k.sort()
        return arr_k[:k]

    return divide(arr, 0, len(arr) - 1, k)

最后提交測試，處于中上游水平。這道題目比較經典的做法是使用堆排序的方法，得到的最小 k 個數，大家可以課后使用堆排序的方法完成。

3. 漂亮數組

這一題是 leetcode 上算法部分的第932題：漂亮數組。該題的描述如下：

對于某些固定的 N，如果數組 A 是整數 1, 2, …, N 組成的排列，使得：對于每個 i < j，都不存在 k 滿足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。那么數組 A 是漂亮數組。給定 N，返回任意漂亮數組 A（保證存在一個）。

示例 1：

輸入：4
輸出：[2,1,4,3]

示例 2：

輸入：5
輸出：[3,1,2,5,4]

這道題官方給出了一個非常精妙的分治思路，接下來我們一起來領略下分治的魅力。和前面所有的解答一樣，先對數組進行分解，然后分別通過子問題的解來得到原問題的解。

首先是原問題的解是：得到長度為 N 的漂亮數組，該數組的元素是 1~N 的一個全排列。我們定義這樣一個方法，實現這個問題的解：f(N)，接下來對 N 進行對半分解，得到 f((N + 1) // 2) 和 f(N // 2)，它們分別返回長度為 ( N +１) // 2 和 N // 2 的漂亮數組，那么如何將這兩個漂亮數組組成長度為 N 的漂亮數組呢？

注意： f((N + 1) // 2) 得到的漂亮數組是 1~((N + 1) // 2) 的一個全排列， 而 f(N // 2) 得到的漂亮數組是 1~(N // 2) 的全排列，而最終 f(N) 得到的漂亮數組為 1~N 的一個全排列。

官方指出了該漂亮數組的一個性質：如果某個數組 [a₁, a₂, … ,a_n] 是漂亮的，那么數組 [ka<sub>1</sub>+b, ka<sub>2</sub>+b, ... ,ka<sub>n</sub>+b] 也是漂亮的。假設我們將 f((N + 1) // 2) 和 f(N // 2) 得到的結果組合到一起：
$x = [a_1,a_2,\cdots,a_\frac{N+1}{2},b_1,b_2,\cdots,b_\frac{N}{2}]$
我們注意到，前半部分為漂亮數組，后半部分也是漂亮數組，也就是滿足漂亮的特點。現在還需要兩個條件：

• 將數組變成 1~N 的全排列；
• 保證從 a 數組中取一個 a[i]，從 b 數組中取一個 b[j]，然后不存在 i<k<(N+1)//2 + j，使得 x[k] * 2 = a[i] + b[j]。

如何能實現上述兩個條件呢？看公式：A[k] * 2 = A[i] + A[j]， 發現 A[k] * 2 為偶數，那么只要 A[i] 和 A[j] 分別為奇數和偶數，那么這個式子就不會成立。對于如何滿足上面的條件二，我們只需要通過將 a 的漂亮數組進行奇數映射即可，同樣對于 b 的漂亮數組進行偶數映射即可：

x1 = [2 * x - 1 for x in a]   # 得到奇數
x2 = [2 * x for x in b]       # 得到奇數

主要到這樣映射后，得到的 x1 和 x2 仍舊是漂亮數組，且 x1 為奇數數組，x2為偶數數組。從 x1 和 x2 中各自選一個元素 ，永遠不會由這兩個元素的中間元素 m 滿足：m * 2 = x1 + x2 （因為 x1 為奇數，x2 為偶數，而 m * 2 為偶數）。

更巧的是，這樣映射之后，x1 和 x2 中的元素正好是 1~N 的一個全排列，這樣就通過兩個子問題的解最終得到了原問題 f(N) 的解。是不是非常巧妙？下面官方題解給出的關于上述分治算法的精妙解答，用的正是上面的分治思路：

def beautifulArray(N):
    memo = {1: [1]}
    def f(N):
        if N not in memo:
            # 得到長度為 (N + 1) // 2 的漂亮數組
            odds = f((N + 1) // 2)
            # 得到長度為 N // 2 的漂亮數組
            evens = f(N // 2)
            # 組合成長度為 N 的漂亮數組，基于的上面討論的規則
            memo[N] = [2 * x - 1 for x in odds] + [2 * x for x in evens]
        return memo[N]
    return f(N)

總的來說，分治法有很多應用場景，且經常使用會結果遞歸來實現。但并不是所有的題目都適合分治法，我們要看通過分割問題規模而得到的子問題的解，究竟能不能合并得到原問題的解，這才分治算法的核心。

4. 小結

本小節使用了 3 道 leetcode 編程題進行了分治算法的實戰練習，通過這些題目可以加深我們對分治算法的理解及應用。在 leetcode 以及其他 OJ 平臺上還有很多這樣有意思的題目，大家要勤于練習。Python 基礎算法教程的內容就到這里結束了，感謝大家的閱讀與陪伴，咱們青山不改，江湖再會。