《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語言描述） 課件 第4章分治法2

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

…

ai

…

amidamid+1

…

aj

…

ahighmaxLeftSummaxRightSum（a）遞歸求出maxLeftSum和maxRightSummax3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)（c）求出a序列中最大連續(xù)子序列的和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為中心的最大連續(xù)子序列和為20（c）結(jié)果=max3(11，13，20)=20示例4/331 defmaxSubSum51(a,low,high): #分治算法2 iflow==high:returnmax(a[low],0) #子序列只有一個(gè)元素時(shí)3 mid=(low+high)//2 #求中間位置4 maxLeftSum=maxSubSum51(a,low,mid)

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

#求右邊的最大連續(xù)子序列之和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序列中最大連續(xù)子序列和17 returnmaxSubSum51(a,0,len(a)-1)7/33T(n)=1 當(dāng)n=1T(n)=2T(n/2)+n

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

nums，設(shè)計(jì)一個(gè)算法找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

例如，nums={-2，1，-3，4，-1，2，1，-5，4}，答案為6，對應(yīng)的連續(xù)子數(shù)組是{4，-1，2，1}。

要求設(shè)計(jì)如下方法：

def

maxSubArray(self,

nums:

List[int])

->

int4.4.2實(shí)戰(zhàn)—最大子序列和（LeetCode53★）9/33采用4.4.1節(jié)的分治法思路，由于這里的最大連續(xù)子序列至少含一個(gè)元素，為此做兩點(diǎn)修改：當(dāng)區(qū)間nums[low..high]中只有一個(gè)元素時(shí)返回nums[low]?？紤]最大連續(xù)子序列跨越中間位置nums[mid]元素時(shí)，左段的最大連續(xù)元素和maxLeftBorderSum初始值置為nums[mid]，右段的最大連續(xù)元素和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]

#子序列只有一個(gè)元素時(shí)9

mid=(low+high)//2

#求中間位置10

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

#求左邊的最大連續(xù)子序列之和11

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

#求右邊的最大連續(xù)子序列之和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上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為1580ms，消耗空間為29.9MB。14/33問題描述：給定一個(gè)大小為n的數(shù)組nums，設(shè)計(jì)一個(gè)算法求其中的多數(shù)元素。

多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于

n/2

的元素?？梢约僭O(shè)中給定的非空數(shù)組中總是存在多數(shù)元素。

例如數(shù)組為{3，2，3}，結(jié)果為3。

要求設(shè)計(jì)如下方法：

def

majorityElement(self,

nums)

->

int:4.4.3實(shí)戰(zhàn)—多數(shù)元素（LeetCode169）15/33nums[0..n-1]中一定存在多數(shù)元素。當(dāng)n=1，nums[0]就是多數(shù)元素，否則針對nums[low..high]采用分治法策略如下：分解：求出mid=(low+high)/2，將nums[low..high]分解成兩個(gè)子序列nums[low..mid]和nums[mid+1..high]，即將整個(gè)問題分解為兩個(gè)相似的子問題。求解子問題：求出nums[low..mid]中多數(shù)元素為leftmaj，求出nums[mid+1..high]中多數(shù)元素為rightmaj。合并：如果leftmaj=rightmaj，則它一定就是nums[low..high]的多數(shù)元素。否則求出leftmaj在nums[low..high]的出現(xiàn)次數(shù)leftcnt，rightmaj在nums[low..high]的出現(xiàn)次數(shù)rightcnt，若leftcnt>rightcnt，則leftmaj是多數(shù)元素，否則rightmaj是多數(shù)元素。解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上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為104ms，消耗空間為17MB。20/33問題描述：含n個(gè)整數(shù)數(shù)組nums（0≤n≤3000，-10^5≤nums[i]≤10^5）。設(shè)計(jì)一個(gè)算法判斷nums中是否存在三個(gè)元素a，b，c，使得a+b+c=0成立。要求找出所有和為0且不重復(fù)的三元組。

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

要求設(shè)計(jì)如下方法：

def

threeSum(self,

nums)

->

List[List[int]]:4.4.4實(shí)戰(zhàn)—三數(shù)之和（LeetCode15★★）21/33解以例4-2為基礎(chǔ)，先將nums數(shù)組元素遞增排序。用i遍歷nums，對于每個(gè)nums[i]，在nums[i+1..n-1]中查找元素和為-nums[i]的元素對，再加上nums[i]構(gòu)成一個(gè)滿足要求的三元組，對于每個(gè)元素都需要跳過重復(fù)的元素。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 #跳過重復(fù)的元素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

#和太小，向右移動(dòng)13

elif

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

else:

#找到一個(gè)三元組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 #跳過重復(fù)的元素nums[low]20

high-=121

while

low<high

and

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

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

return

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