《算法设计与分析基础》（Python语言描述） 课件 第4章分治法2

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]