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

第4章分而治之—分治法4.1分治法概述4.2求解排列问题CONTENTS提纲4.3求解查找问题4.4求解组合问题1/75分治从字面上的解释就是“分而治之”。把一个复杂的问题分成k（1<k≤n）个相同或相似的子问题，再把子问题分成更小的子问题，以此类推，直到可以直接求解为止，原问题的解可以通过子问题的解合并得到。4.1.1什么是分治法4.1分治法概述2/75分治法求解问题的特征问题的规模缩小到一定程度就可以容易地解决。问题可以分解为若干个规模较小的相似问题

基本前提。利用子问题的解可以合并为问题的解

关键。问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

分治法效率。3/75分治算法的求解过程子问题1的解原问题子问题1子问题2子问题k…分子问题2的解子问题k的解治原问题的解合并4/751 defdivide-and-conquer(P): #分治算法框架2 if|P|≤n0:returnadhoc(P)3 将P分解为较小的子问题P1，P2，…，Pk4 foriinrange(1,k+1): #循环处理k次5 yi=divide-and-conquer(Pi) #递归解决Pi6 returnmerge(y1，y2，…，yk) #合并子问题4.1.2分治算法框架5/75【例4-1】给定一棵采用二叉链存储的二叉树b，设计一个算法求其中叶子结点的个数。解设f(b)用于求二叉树b中叶子结点的个数bf(b.left)f(b)f(b.right)f(b)=0 当b=Nonef(b)=1 当b为叶子结点f(b)=f(b.left)+f(b.right) 其他6/751 defleafnodes(b): #求二叉树b中的叶子结点个数2 ifb==None:return0 #空树3 ifb.left==Noneandb.right==None:return1 #叶子4 else:returnleafnodes(b.left)+leafnodes(b.right) #其他f(b)=0 当b=Nonef(b)=1 当b为叶子结点f(b)=f(b.left)+f(b.right) 其他7/754.2.1快速排序4.2求解排列问题R[s]R[s+1]…

R[t]无序区一趟划分R[s]

…

R[i-1]R[i+1]…

R[t]无序区1无序区2R[i]归位所有元素≥basebase所有元素≤basebase8/75分解：将原序列R[s..t]分解成两个子序列R[s..i-1]和R[i+1..t]，其中i为划分的基准位置。即将整个问题分解为两个子问题。求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回；否则递归地求解各个子问题。合并：由于每个子问题的排序结果直接存放在数组a中，合并步骤不需要执行任何操作。快速排序的分治策略9/752517106943812571069438①345691078②43③691078④87910⑤78⑥10/75划分算法设计1）移动法as……at>base…j≤base元素区间basei<base≥base元素区间交换11/7535142base43210示例ij划分完成12/751 defPartition1(a,s,t): #划分算法12 i,j=s,t3 base=a[s] #以表首元素为基准4 whilei<j: #向中间遍历,直至i=j为止5 whilej>ianda[j]>=base:j-=1 #从后向前遍历6 ifj>i:7 a[i]=a[j] #a[j]前移覆盖a[i]8 i+=19 whilei<janda[i]<=base:i+=1 #从前向后遍历10 ifi<j:11 a[j]=a[i]; #a[i]后移覆盖a[j]12 j-=113 a[i]=base #基准归位14 returni #返回基准归位的位置13/752）区间划分法>base元素区间as…aiai+1…ataj≤base时交换aj…j≤base元素区间base>base元素区间as…aiai+1…ataj…≤base元素区间base交换14/7535142base43210示例ij划分完成315/751 defPartition2(a,s,t): #划分算法22 i,j=s,s+13 base=a[s] #以表首元素为基准4 whilej<=t: #j从s+1开始遍历其他元素5 ifa[j]<=base: #找到≤基准的元素a[j]6 i+=1 #扩大≤base区间7 ifi!=j:a[i],a[j]=a[j],a[i] #将a[i]与a[j]交换8 j+=1 #继续扫描9 a[s],a[i]=a[i],a[s] #基准a[s]和a[i]进行交换10 returniend16/75快速排序算法设计递归模型f(R，s，t)≡不做任何事情

R[s..t]为空或仅有一个元素时f(R，s，t)≡i=Partition1(R，s，t); 其他情况（也可以调用Partition2）f(R，s，i-1);f(R，i+1，t);R[s]R[s+1]…

R[t]无序区一趟划分R[s]

…

R[i-1]R[i+1]…

R[t]无序区1无序区2R[i]归位所有元素≥basebase所有元素≤basebase17/751 defQuickSort11(a,s,t): #对a[s..t]的元素进行快速排序2 ifs<t: #表中至少存在两个元素的情况3 i=Partition1(a,s,t) #可以使用划分算法中的任意一种4 QuickSort11(a,s,i-1) #对左子表递归排序5 QuickSort11(a,i+1,t) #对右子表递归排序67 defQuickSort1(a): #递归算法：快速排序8 QuickSort11(a,0,len(a)-1)平均时间复杂度是O(nlog2n)。18/75问题描述：给定一个含n（0≤n≤100000）个整数的数组arr和整数k（0≤k≤min(100000，n)），设计一个算法求arr中最小的k个数，以任意顺序返回这k个数均可。

例如，arr={1，3，5，7，2，4，6，8}，k=4，返回结果是{1，2，3，4}。

要求设计如下方法：def

smallestK(self,arr,k)

->

List[int]:4.2.2实战—最小k个数（面试题17.14★★）19/75解假设整数无序序列用a[0..n-1]表示，若将a递增排序，则第k（1≤k<n）小的元素就是a[k-1]。实际上没有必要对整个序列排序，如果能够找到这样的元素a[i]，它是归位的元素且其序号恰好是k-1即k-1=i。则a[0..k-1]就是最小的k个数。20/75

采用快速排序的划分思想在无序序列a[s..t]中查找第k小元素的过程如下：（1）若s≥t，即序列中只有一个元素，返回。（2）若s<t，表示序列中有两个或以上的元素，以基准为中心将其划分为a[s..i-1]和a[i+1..t]两个子序列，基准a[i]已归位，分为以下3种情况：若k-1=i，a[i]即为所求，返回a[0..k-1]。若k-1<i，说明第k小元素应在a[s..i-1]子序列中，在该子序列中继续查找。若k-1>i，说明第k小元素应在a[i+1..t]子序列中，在该子序列中继续查找。21/75例如，a={3，2，1，5，4}，k=2，求解过程：543

i=2，k-1<i3215412

i=0，k-1>i12一个元素，即为所求22/751 class

Solution:2

def

smallestK(self,arr,k)

->

List[int]:3

n=len(arr)4

ans=[0]*k5

if

n==0

or

k==0:return

ans6

if

n==k:return

arr7

self.QuickSelect(arr,0,n-1,k)8

for

i

in

range(0,k):9

ans[i]=arr[i]10

return

ans1112

def

Partition(self,a,s,t):

#划分算法:同前面的Partition1或者Partition223/7514

def

QuickSelect(self,a,s,t,k):

#求第k小元素15

if

s<t:

#至少存在2个元素的情况16

i=self.Partition(a,s,t)

17

if

k-1==i:18

return

a[i]19

elif

k-1<i:20

return

self.QuickSelect(a,s,i-1,k)21

else:22

return

self.QuickSelect(a,i+1,t,k)时间复杂度为O(n)。上述程序提交结果为通过，运行时间为76ms，消耗空间为20.3MB。24/75已知由n（n≥2）个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C、C++描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。2016年全国计算机学科专业考研题示例25/75查找第n/2小的元素递归快速排序将A递增排序，前

n/2个元素放在A1中，其他放在A2中将最小的

n/2个元素放在A1中，其他放在A2中解26/754.2.3归并排序归并排序的基本思想是先将R[0..n-1]看成是n个长度为1的有序表，依次将相邻的k（k≥2）个有序子表成对归并，…。k=2时每次归并两个相邻的有序子表，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。27/751 defMerge(a,low,mid,high): #归并两个相邻有序子序列2 a1=[] #用做临时表3 i,j=low,mid+1

#i、j分别为两个子表的下标4 whilei<=midandj<=high: #在子表1和子表2均未遍历完时循环5 ifa[i]<=a[j]: #将子表1中的元素归并到a16 a1.append(a[i]);i+=17 else: #将子表2中的元素归并到a18 a1.append(a[j]);j+=19 whilei<=mid: #将子表1余下元素改变到a110 a1.append(a[i]);i+=111 whilej<=high: #将子表2余下元素改变到a112 a1.append(a[j]);j+=113 i=low14 forxina1: #将a1复制回a中15 a[i]=x;i+=1R[low..mid]和R[mid+1..high]

R[low..high]28/75采用递归实现二路归并排序算法，属于典型的二分法算法。设归并排序的当前区间是R[low..high]，其分治策略如下：分解：将当前序列R[low..high]一分为二，即求mid=(low+high)/2，分解为两个子序列R[low..mid]和R[mid+1..high]（前者元素个数≥后者元素个数）。子问题求解：递归地对两个相邻子序列R[low..mid]和R[mid+1..high]二路归并排序。其终止条件是子序列长度为1或者0（只有一个元素的子序列者空表可以看成有序表）。合并：与分解过程相反，将已排序的两个子序列R[low..mid]（有序段1）和R[mid+1..high]（有序段2）归并为一个有序序列R[low..high]。29/75251710694382517106943825171025125

2512571071012571069438694696946938383468912345678910顶递归二路归并排序30/751 defMergeSort1(a,low,high): #被MergeSort调用2 iflow<high: #子序列有两个或以上元素3 mid=(low+high)//2 #取中间位置4 MergeSort1(a,low,mid) #对a[low..mid]排序5 MergeSort1(a,mid+1,high) #对a[mid+1..high]排序6 Merge(a,low,mid,high) #将两有序子序列合并78 defMergeSort(a): #自顶向下的二路归并算法9 MergeSort1(a,0,len(a)-1)时间复杂度为O(nlog2n)。31/75问题描述：在数组a中两个不同元素a[i]和a[j]，若i<j，并且a[i]>a[j]，称（a[i]，a[j]）为一个逆序对。

设计一个算法求数组nums（0≤长度n≤50000）中逆序对的总数。

例如，nums={7，5，6，4}，逆序对有（7，5），（7，6），（7，4），（5，4），（6，4），结果为5。

要求设计如下方法：

def

reversePairs(self,

nums:

List[int])

->

int4.2.4实战—数组中的逆序对（剑指Offer51★★★）32/75二路归并排序：在合并过程中求逆序数。解若a[i]>a[j]（归并a[j]），看出前半部分中a[i..mid]都比a[j]大，对应的逆序对个数为mid-i+1。②若a[i]≤a[j]（归并a[i]），不产生逆序对。a[low]…

a[i]…a[mid]a[i]>a[j]a[mid+1]…a[j]…a[high]a[i..mid]>a[j]

有逆序对(a[i]，a[j])，(a[i+1]，a[j])，…，(a[mid]，a[j])，共mid-i+1个有序段1有序段233/751 class

Solution:2

def

reversePairs(self,

nums:

List[int])

->

int:3

n=len(nums)4

if

n==0

or

n==1:return

05

self.ans=06

self.MergeSort1(nums,0,n-1)7

return

self.ans34/759

def

Merge(self,a,low,mid,high):#归并两个相邻有序子序列10

a1=[]

#用做临时表11

i,j=low,mid+1

#i、j分别为两个子表的下标12

while

i<=mid

and

j<=high:

#两个子表均未遍历完时循环13

if

a[i]<=a[j]:

#将子表1中的元素归并到a114

a1.append(a[i]);i+=115

else:

#将子表2中的元素归并到a116

a1.append(a[j]);j+=117

self.ans+=mid-i+1

#累计逆序数a[low]…

a[i]…a[mid]a[i]>a[j]a[mid+1]…a[j]…a[high]a[i..mid]>a[j]

有逆序对(a[i]，a[j])，(a[i+1]，a[j])，…，(a[mid]，a[j])，共mid-i+1个有序段1有序段235/7518

while

i<=mid:

#将子表1余下元素改变到a119

a1.append(a[i]);i+=120

while

j<=high:

#将子表2余下元素改变到a121

a1.append(a[j]);j+=122

i=low23

for

x

in

a1:

#将a1复制回a中24

a[i]=x;i+=136/7526

def

MergeSort1(self,a,low,high):

#二路归并排序27

if

low<high:

#子序列有两个或以上元素28

mid=(low+high)//2

#取中间位置29

self.MergeSort1(a,low,mid)30

self.MergeSort1(a,mid+1,high)31

self.Merge(a,low,mid,high)

#将两有序子序列合并提交结果为通过，运行时间为1172ms，消耗空间为20.7MB。37/754.3.1查找最大和次大元素4.3求解查找问题对于给定的含有n个整数的无序序列，求这个序列中最大和次大的两个不同的元素。例如：

a=（1，3），max1=3，max2=1。

a=（1，3，3），max1=3，max2=3。

a=（1），max1=3，max2=-∞。38/75分治法求最大元素max1和次大元素max2的过程如下：若a[low.high]只有一个元素：max1=a[low]，max2=-INF（-∞）。若a[low.high]中只有两个元素：max1=max(a[low]，a[high])，max2=min(a[low]，a[high])。分解并求解子问题：且若a[low.high]中只有两个以上元素，按中间位置mid=(low+high)/2划分为a[low..mid]和a[mid+1..high]左右两个区间（注意左区间包含a[mid]元素）。递归求出左区间最大元素lmax1和次大元素lmax2；递归求出右区间最大元素rmax1和次大元素rmax2。合并：若lmax1>rmax1，则max1=lmax1，max2=max(lmax2，rmax1)，否则max1=rmax1，max2=max(lmax1，rmax2)。解39/75例如，a[0..4]={5，2，1，4，3}（1）mid=(0+4)/2=2，划分为左区间a[0..2]={5，2，1}，右区间a[3..4]={4，3}。（2）递归在左区间中求出lmax1=5，lmax2=2，递归在右区间中求出rmax1=4，rmax2=3。合并操作是，max1=max(lmax1，rmax1)=5，max2=max(lmax2，rmax1)=4。52143lmax1=5lmax2=252143rmax1=4rmax2=3max1=max(5,4)=5max2=max(2,4)=4合并40/751 INF=0x3f3f3f3f #表示∞2 defmax21(a,low,high): #被max2调用3 ans=[0,0]4 iflow==high: #区间只有一个元素5 ans[0],ans[1]=a[low],-INF6 eliflow==high-1: #区间只有两个元素7 ans[0],ans[1]=max(a[low],a[high]),min(a[low],a[high])41/758 else:9 mid=(low+high)//210 leftans=max21(a,low,mid) #左区间求leftans11 rightans=max21(a,mid+1,high) #右区间求rightans12 ifleftans[0]>rightans[0]:13 ans[0]=leftans[0]14 ans[1]=max(leftans[1],rightans[0]) #合并求次大元素15 else:16 ans[0]=rightans[0]17 ans[1]=max(leftans[0],rightans[1]) #合并求次大元素18 returnans42/75T(1)=O(1)T(n)=2T(n/2)+O(1) 当n>2时，合并的时间为O(1)时间复杂度为O(n)。43/754.3.2二分查找1 defBinSearch11(a,low,high,k): #递归二分查找算法2 iflow<=high:

#当前区间存在元素时3 mid=(low+high)//2 #求查找区间的中间位置4 ifk==a[mid]:

#找到后返回下标mid5 returnmid6 elifk<a[mid]:

#k<a[mid]:左区间查找7 returnBinSearch11(a,low,mid-1,k)8 else: #k>a[mid]:在右区间查找9 returnBinSearch11(a,mid+1,high,k)10 else:return-1 #查找失败返回-11112 defBinSearch1(a,k): #二分查找算法13 returnBinSearch11(a,0,len(a)-1,k)R递增有序，查找k的序号44/75循环不变式：若k存在于R[0..n-1]，那么它一定在查找区间R[low..high]中。初始化：循环开始之前查找区间R[low..high]就是R[0..n-1]，显然成立。保持：每轮循环开始前，k存在于查找区间R[low..high]中，每轮循环是先计算mid=(low+high)/2，操作如下：①k=R[mid]，查找到了值为k的元素，直接返回其序号mid。②k<R[mid]，值为k的元素只可能存在于R[low..mid-1]中。③k>R[mid]，值为k的元素只可能存在于R[mid+1..high]中。每次减小查找区间长度，最后由1（low=high）变为0（low>high）。终止：循环结束时low>high成立，查找区间为空，表示k不存在于所有步骤的查找区间中，再结合每一步排除的部分元素中也不可能有k，因此k不存在于R中。二分查找算法的正确性证明45/751 defBinSearch2(a,k): #二分查找迭代算法Ⅰ2 low,high=0,len(a)-13 whilelow<=high:

#当前区间存在元素时循环4 mid=(low+high)//2 #求查找区间的中间位置5 ifk==a[mid]:

#找到后返回其下标mid6 returnmid7 elifk<a[mid]: #k<a[mid]:左区间中查找8 high=mid-19 else: #k>a[mid]:右区间中查找10 low=mid+111 return-1 #查找失败返回-1等价的迭代二分查找算法46/75【例4-2】设nums整数数组是递增有序的并且所有元素不同，给定一个整数k，求所有两个不同元素和等于k的元素对。47/75若sum<k，由于nums[high]是最大元素，对应的小问题是f(nums，low+1，high，k)。若sum>k，由于nums[low]是最小元素，对应的小问题是f(nums，low，high-1，k)。若sum=k，找到一个解，继续查找其他解，对应的小问题是f(nums，low+1，high-1，k)。解设f(nums，low，high，k)用于求nums[low..high]中和为k的元素对，它是大问题，求出sum=nums[low]+nums[high]，分为3种情况：48/751 defsumk(nums,k): #迭代分治算法2 ans=[]3 low,high=0,len(nums)-14 whilelow<high:5 sum=nums[low]+nums[high]6 ifsum<k:low+=1 #和太小，向右移动7 elifsum>k:high-=1 #和太大，向左移动8 else: #找到一个二元组tmp9 tmp=[nums[low],nums[high]]10 ans.append(tmp) #将tmp添加到ans中11 low+=1;high-=112 returnans49/75当递增有序序列a[0..n-1]中含相同元素时，如果按照前面的基本二分查找可以找到k的位置，但如果有多个k，此时不能确定是哪一个为k的元素序号，很多情况是查找第一个大于等于k的元素序号，该序号称为R中k的插入点。例如a={1，2，2，4}，n=4，元素序号为0～3，-1的插入点是0，2的插入点是1，3的插入点是3，4的插入点是3，5的插入点是4。设计一个求k的插入点的算法。4.3.3二分查找扩展50/75若k=a[mid]，a[mid]不一定是第一个大于等于k的元素，继续在左区间查找，则新查找区间修改为a[low..mid-1]。若k<a[mid]，a[mid]不一定是第一个大于等于k的元素，继续在左区间查找，同样新查找区间修改为a[low..mid-1]。若k>a[mid]，a[mid]一定不是第一个大于等于k的元素，继续在右区间查找，则新查找区间修改为a[mid+1..high]。解法1（查找到区间为空）基于基本二分查找思路，设a[low..high]为当前的查找区间，当查找区间非空时求出mid=

(low+high)/2

，然后将k和a[mid]比较，分为3种情况：51/751 definsertpoint1(a,k): #查找第一个大于等于k的元素位置2 low,high=0,len(a)-13 whilelow<=high: #当前区间至少有一个元素时4 mid=(low+high)//2 #求查找区间的中间位置5 ifk<=a[mid]:

#k<=a[mid]6 high=mid-1 #在a[low..mid-1]中查找7 else:8 low=mid+1 #在a[mid+1..high]中查找9 returnlow #返回low或high+152/75若k=a[mid]，a[mid]不一定是第一个大于等于k的元素，继续在左区间查找，但a[mid]可能是第一个等于k的元素，所以左区间应该包含a[mid]，则新查找区间修改为a[low..mid]。若k<a[mid]，a[mid]不一定是第一个大于等于k的元素，继续在左区间查找，但a[mid]可能是第一个大于k的元素，所以左区间应该包含a[mid]，则新查找区间修改为a[low..mid]。若k>a[mid]，a[mid]一定不是第一个大于等于k的元素，继续在右区间查找，则新查找区间修改为a[mid+1..high]。解法2（查找到区间仅含一个元素）a中k插入点的范围是0～n，采用扩展二分查找方法，若查找区间为a[low..high]（从a[0..n]开始），求出mid=(low+high)/2，元素比较分为3种情况：53/75问题描述：设计一个算法在所有相邻元素值不相同的整数数组nums中（即对于所有有效的i都有nums[i]≠nums[i+1]）找峰值元素并返回其索引。

峰值元素是指其值大于左右相邻值的元素。假设nums[-1]=nums[n]=-∞，如果包含多个峰值，返回任何一个峰值索引即可。

例如，nums[0..6]={1，2，1，3，5，6，4}，结果是1或5。

要求设计如下方法：

def

findPeakElement(self,

nums)

->

int12135644.3.4实战—寻找峰值（LeetCode162★★）54/75a[mid]<a[mid+1]a[low]<…<a[mid]<a[mid+1]<…<峰值

>…>a[high](b)情况②峰值在右边（不含mid）a[mid]>a[mid+1]a[low]<…<峰值

>…>a[mid]>a[mid+1]>…>a[high](a)情况①峰值在左边（可能含mid）解法1（查找到区间为空）55/75a[mid]>a[mid+1]a[low]<…<峰值

>…>a[mid]>a[mid+1]>…>a[high]在[0，n-1]中查找第一个满足a[mid]>a[mid+1]条件的mid56/751 class

Solution:2

def

findPeakElement(self,

nums)->int:

#解法13

n=len(nums)4

if

n==1:return

05

low,high=0,n-16

while

low<=high:

#查找区间至少有一个元素时循环7

mid=(low+high)//28

if

mid+1>=n

or

nums[mid]>nums[mid+1]: #峰值在左边9

high=mid-110

else:

#峰值在右边11

low=mid+112

return

low上述程序提交结果为通过，运行时间为28ms，消耗空间为15MB。57/75解法2（查找到区间仅含一个元素)a中k插入点的范围是0～n，设a[low..high]为当前的查找区间（初始化为[0，n]。循环结束查找到区间含一个元素，就是答案。58/751 class

Solution:2

def

findPeakElement(self,

nums)

->

int:

#解法23

n=len(nums)4

if

n==1:return

05

low,high=0,len(nums)6

while

low<high:

#查找区间至少有两个元素时循环7

mid=(low+high)//28

if

mid+1>=n

or

nums[mid]>nums[mid+1]:

#峰值在左边9

high=mid10

else:

#峰值在右边11

low=mid+112

return

low上述程序提交结果为通过，运行时间为32ms，消耗空间为15.1MB。59/75问题描述：对于一个长度为n的有序序列（假设均为递增序列）a[0..n-1]，处于中间位置的元素称为a的中位数（当n为奇数时中位数是唯一的，当n为偶数时有两个中位数，这里指前一个中位数）。

例如，若序列a=（11，13，15，17，19），其中位数是15。若b=（2，4，6，8，20），其中位数为6。

两个等长有序序列的中位数是含它们所有元素的有序序列的中位数，例如a、b两个有序序列的中位数为11。设计一个算法求给定的两个有序序列的中位数。4.3.5查找两个等长有序序列的中位数60/75采用二分法求含有n个有序元素的序列a、b的中位数855（1）若n=1，较小者为中位数。解61/75（2）n>1分为3种情况。分别求出a、b的中位数a[m1]和b[m2]：①若a[m1]=b[m2]，则a[m1]或b[m2]即为所求中位数，算法结束。1，3，5，6，92，3，5，8，10562/75②若a[m1]<b[m2]，则舍弃序列a中前半部分（较小的一半），同时舍弃序列b中后半部分（较大的一半）要求舍弃的长度相等。1，3，4，6，92，3，5，8，104，6，92，3，54继续求63/75③若a[m1]>b[m2]，则舍弃序列a中后半部分（较大的一半），同时舍弃序列b中前半部分（较小的一半），要求舍弃的长度相等。舍弃一半即

n/2

个元素。1，3，5，6，92，3，4，8，101,3,54，8，104继续求64/751 defmidnum1(a,i,b,j,n): #求a[i]和b[j]开头长度为n的中位数2 ifn==1: #两序列均只有一个元素时3 returnmin(a[i],b[j])4 else: #均含两个及以上素时5 m1=i+(n-1)//2 #求a的中位数6 m2=j+(n-1)//2 #求b的中位数7 ifa[m1]==b[m2]:returna[m1] #两中位数相等时8 newn=(n+1)//2 #每个序列保留的元素个数9 ifa[m1]<b[m2]: #当a[m1]<b[m2]时10 returnmidnum1(a,i+n-newn,b,j,newn)

#a取后半部分,b取前半部分11 else: #当a[m1]>b[m2]时12 returnmidnum1(a,i,b,j+n-newn,newn)

#a取前半部分,b取后半部分65/7514 defmidnum(a,b,n): #求两个有序序列a和b的中位数15 returnmidnum1(a,0,b,0,n)T(n)=1 当n=1T(n)=T(n/2)+1

当n>1容易推出，T(n)=O(log2n)。66/75问题描述：共有n（n>3）个硬币，编号为0～n-1，其中有且仅有一个假币，假币与真币的外观相同但重量不同，事先知道假币的重量比真币轻。

现在用一架天平称重，天平称重的硬币数没有限制。设计一个算法找出这个假币，使得称重的次数最少。4.3.6查找假币问题67/75采用三分查找思想。用c[0..n-1]存放n个硬币，其中c[i]表示编号i的硬币重量（真币重量为2，假币重量为1）。算法返回找到的假币编号。解68/75n=1或者n=2直接求解。当n≥3时查找假币为原问题，将所有硬币划分为A、B和C三份，保证A、B中硬币个数相同并且A和C中的硬币个数最多相差1。将A和B称重一次后转换为在A、B或者C中查找假币，对应子问题的规模大约为n/3。简单地说，问题规模为n的原问题，通过一次称重后，要么找到了假币，要么转换为一个问题规模大约为n/3的子问题，相当于求解问题规模每次减少为n/3。查找假币的过程如下：69/75202112232425262728ABC202112A1B1C112n=9，9个硬币编号为0～8，假设硬币重2，其中coins[2]=1。0～80～23～56～80～01～12～2示例70/751 defBalance(c,ia,ib,n): #c[ia]和c[ib]开始的n个硬币称重一次2 sa,sb=0,03 i=ia4 forjinrange(0,n):sa+=c[i];i+=15 i=ib6 forjinrange(0,n):sb+=c[i];i+=17 ifsa<sb:return1 #A轻返回18 elifsa==sb:return0 #A，B重量相同返回09 else:return-1 #B轻返回-171/7511 defspcoin1(coins,i,n): #coins[i..i+n-1](n个)找假币12 ifn==1:returni #剩余1个硬币coins[i]13 elifn==2: #剩余硬币coins[i]和coins[i+1]14 b=Balance(coins,i,i+1,1) #2个硬币称重15 ifb==1:returni #coins[i]是假币16 else:returni+1 #coins[i+1]是假币72/7517 else: #剩余3个或者以上硬币18 k=0 #k为A和B中的硬币个数19 ifn%3==0:k=n//320 elifn%3==1:k=n//321 else:k=n//3+122 ia,ib,ic=i,i+k,i+2*k #分为A,B,C,个数分别为k,k,n-2k23 b=Balance(coins,ia,ib,k) #A,B称重一次24 ifb==0:returnspcoin1(coins,ic,n-2*k) #A,B的重量相同25 elifb==1:returnspcoin1(coins,ia,k) #A轻，假币A中26 else:returnspcoin1(coins,ib,k) #B轻，假币在B中73/7528 defspcoin(coins): #求解算法：在coins中查找较轻的假币29 returnspcoin1(coins,0,len(coins))74/75这里仅仅考虑查找n个硬币中假币时的称重次数，设为C(n)。假设n=3k，n=1时称重0次，当n=3时称重1次，n=9时最多称重次数为2，对应的递推式如下：C(n)=1 当n=3时C(n)=C(n/3)+1 当n>3时

可以推出C(n)=log3n。当n≠3k时，由于A、B和C中硬币个数最多相差1，所以最多称重次数C(n)=

log3n

。例如，n=8时，n%3=2，划分为（3，3，2），称重1次后最坏情况的子问题是n1=3，该子问题称重1次即可，所以总称重次数为

log38

=2。算法分析75/754.1分治法概述4.2求解排列问题CONTENTS提纲4.3求解查找问题4.4求解组合问题第4章分而治之—分治法76/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求解组合问题77/33alow

…

ai

…

amidamid+1

…

aj

…

ahighmaxLeftSummaxRightSum（a）递归求出maxLeftSum和maxRightSummax3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)（c）求出a序列中最大连续子序列的和alow

…

amid

amid+1…

ahighmaxLeftBorderSummaxRightBorderSum+（b）求出maxLeftBorderSum+maxRightBorderSum解78/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示例79/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)

#求右边的最大连续子序列之和80/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)81/3316 defmaxSubSum5(a): #求a序列中最大连续子序列和17 returnmaxSubSum51(a,0,len(a)-1)82/33T(n)=1 当n=1T(n)=2T(n/2)+n

当n>1T(n)=O(nlog2n)算法分析83/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★）84/33采用4.4.1节的分治法思路，由于这里的最大连续子序列至少含一个元素，为此做两点修改：当区间nums[low..high]中只有一个元素时返回nums[low]。考虑最大连续子序列跨越中间位置nums[mid]元素时，左段的最大连续元素和maxLeftBorderSum初始值置为nums[mid]，右段的最大连续元素和maxRightBorderSum初始值置为nums[mid+1]。最后返回3部分的最大值。解85/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)86/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)

#求右边的最大连续子序列之和87/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

ans88/33上述程序提交结果为通过，运行时间为1580ms，消耗空间为29.9MB。89/33问题描述：给定一个大小为n的数组nums，设计一个算法求其中的多数元素。

多数元素是指在数组中出现次数大于

n/2

的元素。可以假设中给定的非空数组中总是存在多数元素。

例如数组为{3，2，3}，结果为3。

要求设计如下方法：

def

majorityElement(self,

nums)

->

int:4.4.3实战—多数元素（LeetCode169）90/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是多数元素。解91/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);92/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)93/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