沈無奇 ·分治算法實(shí)戰(zhàn)
今天我們通過 3 道 leetcode 算法題來實(shí)戰(zhàn)分治法。3道題的難度分別為簡單、中等和中等，各有特色。讓我們一起來領(lǐng)略分治的魅力吧。
1. 連續(xù)數(shù)列
首先看題目，這是 leetcode 中的面試題部分，題目內(nèi)容如下：
給定一個(gè)整數(shù)數(shù)組，找出總和最大的連續(xù)數(shù)列，并返回總和。
示例：
輸入： [-2,1,-3,4,-1,2,1,-5,4]
輸出： 6
解釋： 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
進(jìn)階：如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。
這個(gè)很明顯是一道動(dòng)態(tài)規(guī)劃問題，而且使用動(dòng)態(tài)規(guī)劃方法的時(shí)間復(fù)雜度為 ，空間復(fù)雜度可以優(yōu)化為 。題目描述中已經(jīng)說明了可以使用分治法去求解該問題。那我們就要思考，如何分解問題，如何合并子問題的解。首先定義解決該問題的方法：
def divide(nums, left, right):
"""
返回nums[left:right+1]總和最大的連續(xù)數(shù)列
"""
pass
分解終止條件
當(dāng)數(shù)組為空時(shí)，我們就可以停止分解了，轉(zhuǎn)而合并結(jié)果：
if left == right:
return nums[left]
分解問題
每次將序列對半分割即可，然后使用遞歸得到子問題的解：
# 中間一分為二
mid = (left + right) // 2
# 遞歸法：得到左邊最大子序列和，不包含右邊序列
leftSum = divide(nums, left, mid)
# 遞歸得到右邊最大子序列和，不包含mid及其左邊序列
rightSum = divide(nums, mid + 1, right)
合并子問題的解
這是最關(guān)鍵的一步，上面把序列規(guī)模進(jìn)行對半分割后，我們需要通過左邊序列的解和右邊序列的解一起來得出最終的完整序列的解。
假設(shè)我們定義方法： divide(nums, left, right) 為序列 nums[left:right+1] 中最大連續(xù)子列的和；
進(jìn)行規(guī)模分割，有 mid=(left + right) // 2，那么原來的列表被劃分為兩個(gè)子列表：nums[left, mid+1] 和 nums[mid+1, right]。
此時(shí) divide(nums, left, mid) 結(jié)果表示列表 nums[left:mid+1] 中的最大子序列和，記為 leftSum，而 divide(nums, mid+1, right) 的結(jié)果表示的是 nums[mid+1:right] 中的最大子序列和，記為 rightSum。
那么我們僅拿著左右著兩邊最大子序列和的最大值，即 max(leftSum, rightSum) 來作為原問題的解，是否可行？
顯然是不行的，因?yàn)槿绻瓎栴}的最大連續(xù)子列并不單獨(dú)在左邊和右邊，而可能同時(shí)包含左子列和右子列的元素：
此時(shí)，我們需要考慮如何從左右子序列中找到包含左右子序列元素的最大連續(xù)子序列和。
因?yàn)樾蛄羞B續(xù)，所有會(huì)比較簡單，我們直接從 mid 開始分別往左邊移動(dòng)，計(jì)算包含每個(gè)元素的連續(xù)和 (該元素到 mid 位置的元素全部要包括)，找到最大值，得到 leftMidSum。
右邊的子序列做同樣的操作，得到 rightMidSum。最后這兩個(gè)值的和就是同時(shí)包含左右子序列元素的最大連續(xù)數(shù)列的和：leftMidSum + rightMidSum。
這個(gè)時(shí)候我們在拿這三個(gè)的值進(jìn)行比較，找到最大值，此時(shí)得到的結(jié)果才是原問題的解：max(max(leftSum, rightSum), leftMidSum + rightMidSum)。
上述實(shí)現(xiàn)查找包含左右連續(xù)子序列最大和的方法如下：
# 從找出包含mid的左邊連續(xù)序列的最大值
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)
最后原問題的解為三個(gè)值中的最大值，即：
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的左邊連續(xù)序列的最大值
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)
# 此時(shí)leftMidSum + rightMidSum便是中間包含mid的連續(xù)子序列的最大值
return max(max(leftSum, rightSum), leftMidSum + rightMidSum)
return divide(nums, 0, len(nums) - 1)
這個(gè)執(zhí)行的時(shí)間復(fù)雜度為 ，提交代碼耗時(shí)在所有 Python3 提交中墊底，但是這個(gè)解題的思路卻是很重要的，鍛煉我們分治求解能力。
2. 最小 K 個(gè)數(shù)
來看一道常見的面試題，題目描述如下：
設(shè)計(jì)一個(gè)算法，找出數(shù)組中最小的k個(gè)數(shù)。以任意順序返回這k個(gè)數(shù)均可。
示例：
輸入： 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))；
其實(shí)不用分治法，直接考慮快排之后選擇前 k 個(gè)數(shù)即能通過題解。但是本題我們要換一種思路，使用分治法來解決該題。首先定義解決原問題的方法：
def divide(arr, left, right, k):
"""
找出arr[left:right+1]中的最小k個(gè)數(shù)并返回
"""
pass
終止條件
很明顯，我們要找數(shù)組中最小的 k 個(gè)數(shù)，如果數(shù)組長度為空或者長度小于 k，我們可以直接返回該數(shù)組：
# 注意 left 和 right 用于限定數(shù)組
# 終止條件
if not k:
return []
# 終止條件
if (right - left + 1) <= k:
return arr[left: right + 1]
分解列表
和之前一樣，都是對半分，mid = (left + right) // 2，那么數(shù)組會(huì)被劃分為如下兩個(gè)部分：
arr[left:mid + 1] # 左半部分
arr[mid + 1:right] # 右半部分
對于的子問題的解為：
# 得到左子列的最小k個(gè)數(shù)
arr_left_k = divide(arr, left, mid, k)
# 得到右子列的最小k個(gè)數(shù)
arr_right_k = divide(arr, mid + 1, right, k)
合并子結(jié)果，得到原問題的解
首先定義方法：divide(nums, left, right, k)，該方法會(huì)找出列表 nums[left:right + 1] 中前最小的 k 個(gè)數(shù)。
我們用分治法后，將列表分成兩個(gè)子列：nums[left:mid + 1] 和 nums[mid + 1:right + 1]。這樣方法 divide(nums, left, mid, k) 返回的結(jié)果是左子列中前 k 個(gè)最小值，方法 divide(nums, mid + 1, right, k) 返回的結(jié)果是右邊子列中前 k 個(gè)最小值。
此時(shí)我們知道，整個(gè)數(shù)組的前 k 個(gè)最小值必定在這 2k 個(gè)元素中。那么接下來的問題就是從這兩 k 個(gè)值中找出最小的 k 個(gè)數(shù)即可，簡單點(diǎn)的方式就是快排后取前 k 個(gè)。當(dāng)問題規(guī)模 n 遠(yuǎn)大于 k 時(shí)，我們會(huì)發(fā)現(xiàn)排序所耗時(shí)間 非常小，這樣也決定了該分治算法的高效性。
# 組成2k個(gè)數(shù)的列表
arr_k = []
for i in range(len(arr_left_k)):
arr_k.append(arr_left_k[i])
arr_k.extend(arr_right_k)
# 使用快排方法，取前k個(gè)數(shù)，即為結(jié)果，直接返回
arr_k.sort()
最后返回我們想要的前 k 個(gè)元素即可：
return arr_k[:k]
綜合上述幾點(diǎn)，我們得到了如下完整的 Python 實(shí)現(xiàn)：
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個(gè)數(shù)
arr_left_k = divide(arr, left, mid, k)
# 得到右子列的最小k個(gè)數(shù)
arr_right_k = divide(arr, mid + 1, right, k)
# 組成2k個(gè)數(shù)的列表
arr_k = []
for i in range(len(arr_left_k)):
arr_k.append(arr_left_k[i])
arr_k.extend(arr_right_k)
# 使用快排方法，取前k個(gè)數(shù)，即為結(jié)果，直接返回
arr_k.sort()
return arr_k[:k]
return divide(arr, 0, len(arr) - 1, k)
最后提交測試，處于中上游水平。這道題目比較經(jīng)典的做法是使用堆排序的方法，得到的最小 k 個(gè)數(shù)，大家可以課后使用堆排序的方法完成。
3. 漂亮數(shù)組
這一題是 leetcode 上算法部分的第932題：漂亮數(shù)組。該題的描述如下：
對于某些固定的 N，如果數(shù)組 A 是整數(shù) 1, 2, …, N 組成的排列，使得：對于每個(gè) i < j，都不存在 k 滿足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。那么數(shù)組 A 是漂亮數(shù)組。給定 N，返回任意漂亮數(shù)組 A（保證存在一個(gè)）。
示例 1：
輸入：4
輸出：[2,1,4,3]
示例 2：
輸入：5
輸出：[3,1,2,5,4]
這道題官方給出了一個(gè)非常精妙的分治思路，接下來我們一起來領(lǐng)略下分治的魅力。和前面所有的解答一樣，先對數(shù)組進(jìn)行分解，然后分別通過子問題的解來得到原問題的解。
首先是原問題的解是：得到長度為 N 的漂亮數(shù)組，該數(shù)組的元素是 1~N 的一個(gè)全排列。我們定義這樣一個(gè)方法，實(shí)現(xiàn)這個(gè)問題的解：f(N)，接下來對 N 進(jìn)行對半分解，得到 f((N + 1) // 2) 和 f(N // 2)，它們分別返回長度為 ( N +１) // 2 和 N // 2 的漂亮數(shù)組，那么如何將這兩個(gè)漂亮數(shù)組組成長度為 N 的漂亮數(shù)組呢？
注意： f((N + 1) // 2) 得到的漂亮數(shù)組是 1~((N + 1) // 2) 的一個(gè)全排列， 而 f(N // 2) 得到的漂亮數(shù)組是 1~(N // 2) 的全排列，而最終 f(N) 得到的漂亮數(shù)組為 1~N 的一個(gè)全排列。
官方指出了該漂亮數(shù)組的一個(gè)性質(zhì)：如果某個(gè)數(shù)組 [a1, a2, … ,an] 是漂亮的，那么數(shù)組 [ka<sub>1</sub>+b, ka<sub>2</sub>+b, ... ,ka<sub>n</sub>+b] 也是漂亮的。假設(shè)我們將 f((N + 1) // 2) 和 f(N // 2) 得到的結(jié)果組合到一起：
我們注意到，前半部分為漂亮數(shù)組，后半部分也是漂亮數(shù)組，也就是滿足漂亮的特點(diǎn)?，F(xiàn)在還需要兩個(gè)條件：
- 將數(shù)組變成 1~N 的全排列；
- 保證從 a 數(shù)組中取一個(gè) a[i]，從 b 數(shù)組中取一個(gè)
b[j]，然后不存在i<k<(N+1)//2 + j，使得x[k] * 2 = a[i] + b[j]。
如何能實(shí)現(xiàn)上述兩個(gè)條件呢？看公式：A[k] * 2 = A[i] + A[j]， 發(fā)現(xiàn) A[k] * 2 為偶數(shù)，那么只要 A[i] 和 A[j] 分別為奇數(shù)和偶數(shù)，那么這個(gè)式子就不會(huì)成立。對于如何滿足上面的條件二，我們只需要通過將 a 的漂亮數(shù)組進(jìn)行奇數(shù)映射即可，同樣對于 b 的漂亮數(shù)組進(jìn)行偶數(shù)映射即可：
x1 = [2 * x - 1 for x in a] # 得到奇數(shù)
x2 = [2 * x for x in b] # 得到奇數(shù)
主要到這樣映射后，得到的 x1 和 x2 仍舊是漂亮數(shù)組，且 x1 為奇數(shù)數(shù)組，x2為偶數(shù)數(shù)組。從 x1 和 x2 中各自選一個(gè)元素 ，永遠(yuǎn)不會(huì)由這兩個(gè)元素的中間元素 m 滿足：m * 2 = x1 + x2 （因?yàn)?x1 為奇數(shù)，x2 為偶數(shù)，而 m * 2 為偶數(shù)）。
更巧的是，這樣映射之后，x1 和 x2 中的元素正好是 1~N 的一個(gè)全排列，這樣就通過兩個(gè)子問題的解最終得到了原問題 f(N) 的解。是不是非常巧妙？下面官方題解給出的關(guān)于上述分治算法的精妙解答，用的正是上面的分治思路：
def beautifulArray(N):
memo = {1: [1]}
def f(N):
if N not in memo:
# 得到長度為 (N + 1) // 2 的漂亮數(shù)組
odds = f((N + 1) // 2)
# 得到長度為 N // 2 的漂亮數(shù)組
evens = f(N // 2)
# 組合成長度為 N 的漂亮數(shù)組，基于的上面討論的規(guī)則
memo[N] = [2 * x - 1 for x in odds] + [2 * x for x in evens]
return memo[N]
return f(N)
總的來說，分治法有很多應(yīng)用場景，且經(jīng)常使用會(huì)結(jié)果遞歸來實(shí)現(xiàn)。但并不是所有的題目都適合分治法，我們要看通過分割問題規(guī)模而得到的子問題的解，究竟能不能合并得到原問題的解，這才分治算法的核心。
4. 小結(jié)
本小節(jié)使用了 3 道 leetcode 編程題進(jìn)行了分治算法的實(shí)戰(zhàn)練習(xí)，通過這些題目可以加深我們對分治算法的理解及應(yīng)用。在 leetcode 以及其他 OJ 平臺(tái)上還有很多這樣有意思的題目，大家要勤于練習(xí)。Python 基礎(chǔ)算法教程的內(nèi)容就到這里結(jié)束了，感謝大家的閱讀與陪伴，咱們青山不改，江湖再會(huì)。
2025 imooc.com All Rights Reserved |