4.1分治法概述4.2求解排列問題CONTENTS提綱4.3求解查找問題4.4求解組合問題第4章分而治之—分治法1/33給定一個含n（n≥1）個整數的序列，要求求出其中最大連續子序列的和。序列（-2，11，-4，13，-5，-2）的最大連續子序列和為20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大連續子序列和為16。規定一個序列最大連續子序列和至少是0，如果小于0，其結果為0。4.4.1最大連續子序列和4.4求解組合問題2/33alow

…

ai

…

amidamid+1

…

aj

…

ahighmaxLeftSummaxRightSum（a）遞歸求出maxLeftSum和maxRightSummax3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)（c）求出a序列中最大連續子序列的和alow

…

amid

amid+1…

ahighmaxLeftBorderSummaxRightBorderSum+（b）求出maxLeftBorderSum+maxRightBorderSum解3/33-20111-42133-54-25midmaxLeftSum=11maxRightSum=13（a）遞歸求出maxLeftSum和maxRightSummaxLeftBorderSum=7-201112133-54-25-4-475maxRightBorderSum=131386（b）以-4為中心的最大連續子序列和為20（c）結果=max3(11，13，20)=20示例4/331 defmaxSubSum51(a,low,high): #分治算法2 iflow==high:returnmax(a[low],0) #子序列只有一個元素時3 mid=(low+high)//2 #求中間位置4 maxLeftSum=maxSubSum51(a,low,mid)

#求左邊的最大連續子序列之和5 maxRightSum=maxSubSum51(a,mid+1,high)

#求右邊的最大連續子序列之和5/336 maxLeftBorderSum,lowBorderSum=0,07 foriinrange(mid,low-1,-1): #求左段a[i..mid]最大和8 lowBorderSum+=a[i]9 maxLeftBorderSum=max(maxLeftBorderSum,lowBorderSum)10 maxRightBorderSum,highBorderSum=0,011 forjinrange(mid+1,high+1): #求右段a[mid+1..j]最大和12 highBorderSum+=a[j]13 maxRightBorderSum=max(maxRightBorderSum,highBorderSum)14 returnmax(max(maxLeftSum,maxRightSum),

maxLeftBorderSum+maxRightBorderSum)6/3316 defmaxSubSum5(a): #求a序列中最大連續子序列和17 returnmaxSubSum51(a,0,len(a)-1)7/33T(n)=1 當n=1T(n)=2T(n/2)+n

當n>1T(n)=O(nlog2n)算法分析8/33問題描述：給定一個含n（1≤n≤10^5）個整數的數組

nums，設計一個算法找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

例如，nums={-2，1，-3，4，-1，2，1，-5，4}，答案為6，對應的連續子數組是{4，-1，2，1}。

要求設計如下方法：

def

maxSubArray(self,

nums:

List[int])

->

int4.4.2實戰—最大子序列和（LeetCode53★）9/33采用4.4.1節的分治法思路，由于這里的最大連續子序列至少含一個元素，為此做兩點修改：當區間nums[low..high]中只有一個元素時返回nums[low]。考慮最大連續子序列跨越中間位置nums[mid]元素時，左段的最大連續元素和maxLeftBorderSum初始值置為nums[mid]，右段的最大連續元素和maxRightBorderSum初始值置為nums[mid+1]。最后返回3部分的最大值。解10/331 class

Solution:2

def

maxSubArray(self,

nums:

List[int])

->

int:3

n=len(nums)4

if

n==1:return

nums[0]5

return

self.maxSubSum51(nums,0,n-1)11/337

def

maxSubSum51(self,nums,low,high):

#分治算法8

if

low==high:return

nums[low]

#子序列只有一個元素時9

mid=(low+high)//2

#求中間位置10

maxLeftSum=self.maxSubSum51(nums,low,mid)

#求左邊的最大連續子序列之和11

maxRightSum=self.maxSubSum51(nums,mid+1,high)

#求右邊的最大連續子序列之和12/3312

maxLeftBorderSum,lowBorderSum=nums[mid],013

for

i

in

range(mid,low-1,-1):

#求nums[i..mid]的最大和14

lowBorderSum+=nums[i]15

maxLeftBorderSum=max(maxLeftBorderSum,lowBorderSum)16

maxRightBorderSum,highBorderSum=nums[mid+1],017

for

j

in

range(mid+1,high+1):

#求nums[mid+1..j]的最大和18

highBorderSum+=nums[j]19

maxRightBorderSum=max(maxRightBorderSum,highBorderSum)20

ans=max(max(maxLeftSum,maxRightSum),

maxLeftBorderSum+maxRightBorderSum)21

return

ans13/33上述程序提交結果為通過，運行時間為1580ms，消耗空間為29.9MB。14/33問題描述：給定一個大小為n的數組nums，設計一個算法求其中的多數元素。

多數元素是指在數組中出現次數大于

n/2

的元素。可以假設中給定的非空數組中總是存在多數元素。

例如數組為{3，2，3}，結果為3。

要求設計如下方法：

def

majorityElement(self,

nums)

->

int:4.4.3實戰—多數元素（LeetCode169）15/33nums[0..n-1]中一定存在多數元素。當n=1，nums[0]就是多數元素，否則針對nums[low..high]采用分治法策略如下：分解：求出mid=(low+high)/2，將nums[low..high]分解成兩個子序列nums[low..mid]和nums[mid+1..high]，即將整個問題分解為兩個相似的子問題。求解子問題：求出nums[low..mid]中多數元素為leftmaj，求出nums[mid+1..high]中多數元素為rightmaj。合并：如果leftmaj=rightmaj，則它一定就是nums[low..high]的多數元素。否則求出leftmaj在nums[low..high]的出現次數leftcnt，rightmaj在nums[low..high]的出現次數rightcnt，若leftcnt>rightcnt，則leftmaj是多數元素，否則rightmaj是多數元素。解16/331 class

Solution:2

def

majorityElement(self,

nums)

->

int:3

n=len(nums)4

if

n==1:return

nums[0]5

return

self.majore(nums,0,n-1);17/337

def

majore(self,nums,low,high): #分治算法8

if

low==high:return

nums[low]9

mid=(low+high)//210

leftmaj=self.majore(nums,low,mid)11

rightmaj=self.majore(nums,mid+1,high)18/3312

if

leftmaj==rightmaj:13

return

leftmaj14

else:15

leftcnt=016

for

i

in

range(low,high+1):17

if

nums[i]==leftmaj:leftcnt+=118

rightcnt=019

for

i

in

range(low,high+1):20

if

nums[i]==rightmaj:rightcnt+=121

if

leftcnt>rightcnt:return

leftmaj22

else:return

rightmaj19/33上述程序提交結果為通過，運行時間為104ms，消耗空間為17MB。20/33問題描述：含n個整數數組nums（0≤n≤3000，-10^5≤nums[i]≤10^5）。設計一個算法判斷nums中是否存在三個元素a，b，c，使得a+b+c=0成立。要求找出所有和為0且不重復的三元組。

例如，nums={-1，0，1，2，-1，-4}，結果為{{-1，-1，2}，{-1，0，1}}。

要求設計如下方法：

def

threeSum(self,

nums)

->

List[List[int]]:4.4.4實戰—三數之和（LeetCode15★★）21/33解以例4-2為基礎，先將nums數組元素遞增排序。用i遍歷nums，對于每個nums[i]，在nums[i+1..n-1]中查找元素和為-nums[i]的元素對，再加上nums[i]構成一個滿足要求的三元組，對于每個元素都需要跳過重復的元素。22/331 class

Solution:2

def

threeSum(self,

nums:

List[int])

->

List[List[int]]:3

n,ans=len(nums),[]4

if

n<3:return

ans

#長度小于3，返回空表5

nums.sort()

#對nums遞增排序6

if

nums[0]>0:return

ans

#首元素大于0，返回空表23/337

for

i

in

range(0,n-2):

#遍歷nums[i]8

if

i>0

and

nums[i]==nums[i-1]:continue #跳過重復的元素nums[i]9

low,high=i+1,n-124/3310

while

low<high:11

sum=nums[low]+nums[high]12

if

sum<-nums[i]:low+=1

#和太小，向右移動13

elif

sum>-nums[i]:high-=1 #和太大，向左移動14

else:

#找到一個三元組tmp15

tmp=[nums[i],nums[low],nums[high]]16

ans.append(tmp)

#將tmp添加到ans中17

low+=118

while

low<high

and

nums[low]==nums[low-1]:

19

low+=1 #跳過重復的元素nums[low]20

high-=121

while

low<high

and

nums[high]==nums[high+1]:22

high-=1 #跳過重復的元素nums[high]23

return

ans25/33上述程序提交結果為通過，運行時間為1056ms，消耗空間為18.1MB。26/33【問題描述】給定若干個二維空間中的點，點集采用數組p存放，任意兩個不同點之間有一個直線距離，求最近的兩個點的距離。4.4.5求最近點對距離27/33對p中所有點按x坐標遞增排序，采用分治法策略求解。解S1S2p[mid].xd3垂直帶形區ddPLPRXYdld2d=min(d1,d2)d=min(d,d3)28/33ddPLlPRdp1[i]p1中的點按y遞增排序。p1中每個點p1[i]在y方向d距離內最多7個點與它的距離小于d。按y遞增排序29/331 defdis(a,b): #求兩個點之間的距離2 returnmath.sqrt(float(a[0]-b[0]