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

第4章分而治之—分治法4.1分治法概述4.2求解排列問題CONTENTS提綱4.3求解查找問題4.4求解組合問題1/75分治從字面上的解釋就是“分而治之”。把一個(gè)復(fù)雜的問題分成k（1<k≤n）個(gè)相同或相似的子問題，再把子問題分成更小的子問題，以此類推，直到可以直接求解為止，原問題的解可以通過子問題的解合并得到。4.1.1什么是分治法4.1分治法概述2/75分治法求解問題的特征問題的規(guī)?？s小到一定程度就可以容易地解決。問題可以分解為若干個(gè)規(guī)模較小的相似問題

基本前提。利用子問題的解可以合并為問題的解

關(guān)鍵。問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題

分治法效率。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): #循環(huán)處理k次5 yi=divide-and-conquer(Pi) #遞歸解決Pi6 returnmerge(y1，y2，…，yk) #合并子問題4.1.2分治算法框架5/75【例4-1】給定一棵采用二叉鏈存儲(chǔ)的二叉樹b，設(shè)計(jì)一個(gè)算法求其中葉子結(jié)點(diǎn)的個(gè)數(shù)。解設(shè)f(b)用于求二叉樹b中葉子結(jié)點(diǎn)的個(gè)數(shù)bf(b.left)f(b)f(b.right)f(b)=0 當(dāng)b=Nonef(b)=1 當(dāng)b為葉子結(jié)點(diǎn)f(b)=f(b.left)+f(b.right) 其他6/751 defleafnodes(b): #求二叉樹b中的葉子結(jié)點(diǎn)個(gè)數(shù)2 ifb==None:return0 #空樹3 ifb.left==Noneandb.right==None:return1 #葉子4 else:returnleafnodes(b.left)+leafnodes(b.right) #其他f(b)=0 當(dāng)b=Nonef(b)=1 當(dāng)b為葉子結(jié)點(diǎn)f(b)=f(b.left)+f(b.right) 其他7/754.2.1快速排序4.2求解排列問題R[s]R[s+1]…

R[t]無序區(qū)一趟劃分R[s]

…

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

R[t]無序區(qū)1無序區(qū)2R[i]歸位所有元素≥basebase所有元素≤basebase8/75分解：將原序列R[s..t]分解成兩個(gè)子序列R[s..i-1]和R[i+1..t]，其中i為劃分的基準(zhǔn)位置。即將整個(gè)問題分解為兩個(gè)子問題。求解子問題：若子序列的長(zhǎng)度為0或?yàn)?，則它是有序的，直接返回；否則遞歸地求解各個(gè)子問題。合并：由于每個(gè)子問題的排序結(jié)果直接存放在數(shù)組a中，合并步驟不需要執(zhí)行任何操作?？焖倥判虻姆种尾呗?/752517106943812571069438①345691078②43③691078④87910⑤78⑥10/75劃分算法設(shè)計(jì)1）移動(dòng)法as……at>base…j≤base元素區(qū)間basei<base≥base元素區(qū)間交換11/7535142base43210示例ij劃分完成12/751 defPartition1(a,s,t): #劃分算法12 i,j=s,t3 base=a[s] #以表首元素為基準(zhǔn)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 #基準(zhǔn)歸位14 returni #返回基準(zhǔn)歸位的位置13/752）區(qū)間劃分法>base元素區(qū)間as…aiai+1…ataj≤base時(shí)交換aj…j≤base元素區(qū)間base>base元素區(qū)間as…aiai+1…ataj…≤base元素區(qū)間base交換14/7535142base43210示例ij劃分完成315/751 defPartition2(a,s,t): #劃分算法22 i,j=s,s+13 base=a[s] #以表首元素為基準(zhǔn)4 whilej<=t: #j從s+1開始遍歷其他元素5 ifa[j]<=base: #找到≤基準(zhǔn)的元素a[j]6 i+=1 #擴(kuò)大≤base區(qū)間7 ifi!=j:a[i],a[j]=a[j],a[i] #將a[i]與a[j]交換8 j+=1 #繼續(xù)掃描9 a[s],a[i]=a[i],a[s] #基準(zhǔn)a[s]和a[i]進(jìn)行交換10 returniend16/75快速排序算法設(shè)計(jì)遞歸模型f(R，s，t)≡不做任何事情

R[s..t]為空或僅有一個(gè)元素時(shí)f(R，s，t)≡i=Partition1(R，s，t); 其他情況（也可以調(diào)用Partition2）f(R，s，i-1);f(R，i+1，t);R[s]R[s+1]…

R[t]無序區(qū)一趟劃分R[s]

…

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

R[t]無序區(qū)1無序區(qū)2R[i]歸位所有元素≥basebase所有元素≤basebase17/751 defQuickSort11(a,s,t): #對(duì)a[s..t]的元素進(jìn)行快速排序2 ifs<t: #表中至少存在兩個(gè)元素的情況3 i=Partition1(a,s,t) #可以使用劃分算法中的任意一種4 QuickSort11(a,s,i-1) #對(duì)左子表遞歸排序5 QuickSort11(a,i+1,t) #對(duì)右子表遞歸排序67 defQuickSort1(a): #遞歸算法：快速排序8 QuickSort11(a,0,len(a)-1)平均時(shí)間復(fù)雜度是O(nlog2n)。18/75問題描述：給定一個(gè)含n（0≤n≤100000）個(gè)整數(shù)的數(shù)組arr和整數(shù)k（0≤k≤min(100000，n)），設(shè)計(jì)一個(gè)算法求arr中最小的k個(gè)數(shù)，以任意順序返回這k個(gè)數(shù)均可。

例如，arr={1，3，5，7，2，4，6，8}，k=4，返回結(jié)果是{1，2，3，4}。

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

smallestK(self,arr,k)

->

List[int]:4.2.2實(shí)戰(zhàn)—最小k個(gè)數(shù)（面試題17.14★★）19/75解假設(shè)整數(shù)無序序列用a[0..n-1]表示，若將a遞增排序，則第k（1≤k<n）小的元素就是a[k-1]。實(shí)際上沒有必要對(duì)整個(gè)序列排序，如果能夠找到這樣的元素a[i]，它是歸位的元素且其序號(hào)恰好是k-1即k-1=i。則a[0..k-1]就是最小的k個(gè)數(shù)。20/75

采用快速排序的劃分思想在無序序列a[s..t]中查找第k小元素的過程如下：（1）若s≥t，即序列中只有一個(gè)元素，返回。（2）若s<t，表示序列中有兩個(gè)或以上的元素，以基準(zhǔn)為中心將其劃分為a[s..i-1]和a[i+1..t]兩個(gè)子序列，基準(zhǔn)a[i]已歸位，分為以下3種情況：若k-1=i，a[i]即為所求，返回a[0..k-1]。若k-1<i，說明第k小元素應(yīng)在a[s..i-1]子序列中，在該子序列中繼續(xù)查找。若k-1>i，說明第k小元素應(yīng)在a[i+1..t]子序列中，在該子序列中繼續(xù)查找。21/75例如，a={3，2，1，5，4}，k=2，求解過程：543

i=2，k-1<i3215412

i=0，k-1>i12一個(gè)元素，即為所求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個(gè)元素的情況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)時(shí)間復(fù)雜度為O(n)。上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為76ms，消耗空間為20.3MB。24/75已知由n（n≥2）個(gè)正整數(shù)構(gòu)成的集合A={ak}（0≤k<n），將其劃分為兩個(gè)不相交的子集A1和A2，元素個(gè)數(shù)分別是n1和n2，A1和A2中元素之和分別為S1和S2。設(shè)計(jì)一個(gè)盡可能高效的劃分算法，滿足|n1-n2|最小且|S1-S2|最大。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C、C++描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2016年全國計(jì)算機(jī)學(xué)科專業(yè)考研題示例25/75查找第n/2小的元素遞歸快速排序?qū)遞增排序，前

n/2個(gè)元素放在A1中，其他放在A2中將最小的

n/2個(gè)元素放在A1中，其他放在A2中解26/754.2.3歸并排序歸并排序的基本思想是先將R[0..n-1]看成是n個(gè)長(zhǎng)度為1的有序表，依次將相鄰的k（k≥2）個(gè)有序子表成對(duì)歸并，…。k=2時(shí)每次歸并兩個(gè)相鄰的有序子表，稱為二路歸并排序。若k>2，即歸并操作在相鄰的多個(gè)有序子表中進(jìn)行，則叫多路歸并排序。27/751 defMerge(a,low,mid,high): #歸并兩個(gè)相鄰有序子序列2 a1=[] #用做臨時(shí)表3 i,j=low,mid+1

#i、j分別為兩個(gè)子表的下標(biāo)4 whilei<=midandj<=high: #在子表1和子表2均未遍歷完時(shí)循環(huán)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復(fù)制回a中15 a[i]=x;i+=1R[low..mid]和R[mid+1..high]

R[low..high]28/75采用遞歸實(shí)現(xiàn)二路歸并排序算法，屬于典型的二分法算法。設(shè)歸并排序的當(dāng)前區(qū)間是R[low..high]，其分治策略如下：分解：將當(dāng)前序列R[low..high]一分為二，即求mid=(low+high)/2，分解為兩個(gè)子序列R[low..mid]和R[mid+1..high]（前者元素個(gè)數(shù)≥后者元素個(gè)數(shù)）。子問題求解：遞歸地對(duì)兩個(gè)相鄰子序列R[low..mid]和R[mid+1..high]二路歸并排序。其終止條件是子序列長(zhǎng)度為1或者0（只有一個(gè)元素的子序列者空表可以看成有序表）。合并：與分解過程相反，將已排序的兩個(gè)子序列R[low..mid]（有序段1）和R[mid+1..high]（有序段2）歸并為一個(gè)有序序列R[low..high]。29/75251710694382517106943825171025125

2512571071012571069438694696946938383468912345678910頂遞歸二路歸并排序30/751 defMergeSort1(a,low,high): #被MergeSort調(diào)用2 iflow<high: #子序列有兩個(gè)或以上元素3 mid=(low+high)//2 #取中間位置4 MergeSort1(a,low,mid) #對(duì)a[low..mid]排序5 MergeSort1(a,mid+1,high) #對(duì)a[mid+1..high]排序6 Merge(a,low,mid,high) #將兩有序子序列合并78 defMergeSort(a): #自頂向下的二路歸并算法9 MergeSort1(a,0,len(a)-1)時(shí)間復(fù)雜度為O(nlog2n)。31/75問題描述：在數(shù)組a中兩個(gè)不同元素a[i]和a[j]，若i<j，并且a[i]>a[j]，稱（a[i]，a[j]）為一個(gè)逆序?qū)Α?/p>

設(shè)計(jì)一個(gè)算法求數(shù)組nums（0≤長(zhǎng)度n≤50000）中逆序?qū)Φ目倲?shù)。

例如，nums={7，5，6，4}，逆序?qū)τ校?，5），（7，6），（7，4），（5，4），（6，4），結(jié)果為5。

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

def

reversePairs(self,

nums:

List[int])

->

int4.2.4實(shí)戰(zhàn)—數(shù)組中的逆序?qū)Γ▌χ窸ffer51★★★）32/75二路歸并排序：在合并過程中求逆序數(shù)。解若a[i]>a[j]（歸并a[j]），看出前半部分中a[i..mid]都比a[j]大，對(duì)應(yīng)的逆序?qū)€(gè)數(shù)為mid-i+1。②若a[i]≤a[j]（歸并a[i]），不產(chǎn)生逆序?qū)Α[low]…

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

有逆序?qū)?a[i]，a[j])，(a[i+1]，a[j])，…，(a[mid]，a[j])，共mid-i+1個(gè)有序段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):#歸并兩個(gè)相鄰有序子序列10

a1=[]

#用做臨時(shí)表11

i,j=low,mid+1

#i、j分別為兩個(gè)子表的下標(biāo)12

while

i<=mid

and

j<=high:

#兩個(gè)子表均未遍歷完時(shí)循環(huán)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

#累計(jì)逆序數(shù)a[low]…

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

有逆序?qū)?a[i]，a[j])，(a[i+1]，a[j])，…，(a[mid]，a[j])，共mid-i+1個(gè)有序段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復(fù)制回a中24

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

def

MergeSort1(self,a,low,high):

#二路歸并排序27

if

low<high:

#子序列有兩個(gè)或以上元素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)

#將兩有序子序列合并提交結(jié)果為通過，運(yùn)行時(shí)間為1172ms，消耗空間為20.7MB。37/754.3.1查找最大和次大元素4.3求解查找問題對(duì)于給定的含有n個(gè)整數(shù)的無序序列，求這個(gè)序列中最大和次大的兩個(gè)不同的元素。例如：

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]只有一個(gè)元素：max1=a[low]，max2=-INF（-∞）。若a[low.high]中只有兩個(gè)元素：max1=max(a[low]，a[high])，max2=min(a[low]，a[high])。分解并求解子問題：且若a[low.high]中只有兩個(gè)以上元素，按中間位置mid=(low+high)/2劃分為a[low..mid]和a[mid+1..high]左右兩個(gè)區(qū)間（注意左區(qū)間包含a[mid]元素）。遞歸求出左區(qū)間最大元素lmax1和次大元素lmax2；遞歸求出右區(qū)間最大元素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，劃分為左區(qū)間a[0..2]={5，2，1}，右區(qū)間a[3..4]={4，3}。（2）遞歸在左區(qū)間中求出lmax1=5，lmax2=2，遞歸在右區(qū)間中求出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調(diào)用3 ans=[0,0]4 iflow==high: #區(qū)間只有一個(gè)元素5 ans[0],ans[1]=a[low],-INF6 eliflow==high-1: #區(qū)間只有兩個(gè)元素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) #左區(qū)間求leftans11 rightans=max21(a,mid+1,high) #右區(qū)間求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) 當(dāng)n>2時(shí)，合并的時(shí)間為O(1)時(shí)間復(fù)雜度為O(n)。43/754.3.2二分查找1 defBinSearch11(a,low,high,k): #遞歸二分查找算法2 iflow<=high:

#當(dāng)前區(qū)間存在元素時(shí)3 mid=(low+high)//2 #求查找區(qū)間的中間位置4 ifk==a[mid]:

#找到后返回下標(biāo)mid5 returnmid6 elifk<a[mid]:

#k<a[mid]:左區(qū)間查找7 returnBinSearch11(a,low,mid-1,k)8 else: #k>a[mid]:在右區(qū)間查找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的序號(hào)44/75循環(huán)不變式：若k存在于R[0..n-1]，那么它一定在查找區(qū)間R[low..high]中。初始化：循環(huán)開始之前查找區(qū)間R[low..high]就是R[0..n-1]，顯然成立。保持：每輪循環(huán)開始前，k存在于查找區(qū)間R[low..high]中，每輪循環(huán)是先計(jì)算mid=(low+high)/2，操作如下：①k=R[mid]，查找到了值為k的元素，直接返回其序號(hào)mid。②k<R[mid]，值為k的元素只可能存在于R[low..mid-1]中。③k>R[mid]，值為k的元素只可能存在于R[mid+1..high]中。每次減小查找區(qū)間長(zhǎng)度，最后由1（low=high）變?yōu)?（low>high）。終止：循環(huán)結(jié)束時(shí)low>high成立，查找區(qū)間為空，表示k不存在于所有步驟的查找區(qū)間中，再結(jié)合每一步排除的部分元素中也不可能有k，因此k不存在于R中。二分查找算法的正確性證明45/751 defBinSearch2(a,k): #二分查找迭代算法Ⅰ2 low,high=0,len(a)-13 whilelow<=high:

#當(dāng)前區(qū)間存在元素時(shí)循環(huán)4 mid=(low+high)//2 #求查找區(qū)間的中間位置5 ifk==a[mid]:

#找到后返回其下標(biāo)mid6 returnmid7 elifk<a[mid]: #k<a[mid]:左區(qū)間中查找8 high=mid-19 else: #k>a[mid]:右區(qū)間中查找10 low=mid+111 return-1 #查找失敗返回-1等價(jià)的迭代二分查找算法46/75【例4-2】設(shè)nums整數(shù)數(shù)組是遞增有序的并且所有元素不同，給定一個(gè)整數(shù)k，求所有兩個(gè)不同元素和等于k的元素對(duì)。47/75若sum<k，由于nums[high]是最大元素，對(duì)應(yīng)的小問題是f(nums，low+1，high，k)。若sum>k，由于nums[low]是最小元素，對(duì)應(yīng)的小問題是f(nums，low，high-1，k)。若sum=k，找到一個(gè)解，繼續(xù)查找其他解，對(duì)應(yīng)的小問題是f(nums，low+1，high-1，k)。解設(shè)f(nums，low，high，k)用于求nums[low..high]中和為k的元素對(duì)，它是大問題，求出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 #和太小，向右移動(dòng)7 elifsum>k:high-=1 #和太大，向左移動(dòng)8 else: #找到一個(gè)二元組tmp9 tmp=[nums[low],nums[high]]10 ans.append(tmp) #將tmp添加到ans中11 low+=1;high-=112 returnans49/75當(dāng)遞增有序序列a[0..n-1]中含相同元素時(shí)，如果按照前面的基本二分查找可以找到k的位置，但如果有多個(gè)k，此時(shí)不能確定是哪一個(gè)為k的元素序號(hào)，很多情況是查找第一個(gè)大于等于k的元素序號(hào)，該序號(hào)稱為R中k的插入點(diǎn)。例如a={1，2，2，4}，n=4，元素序號(hào)為0～3，-1的插入點(diǎn)是0，2的插入點(diǎn)是1，3的插入點(diǎn)是3，4的插入點(diǎn)是3，5的插入點(diǎn)是4。設(shè)計(jì)一個(gè)求k的插入點(diǎn)的算法。4.3.3二分查找擴(kuò)展50/75若k=a[mid]，a[mid]不一定是第一個(gè)大于等于k的元素，繼續(xù)在左區(qū)間查找，則新查找區(qū)間修改為a[low..mid-1]。若k<a[mid]，a[mid]不一定是第一個(gè)大于等于k的元素，繼續(xù)在左區(qū)間查找，同樣新查找區(qū)間修改為a[low..mid-1]。若k>a[mid]，a[mid]一定不是第一個(gè)大于等于k的元素，繼續(xù)在右區(qū)間查找，則新查找區(qū)間修改為a[mid+1..high]。解法1（查找到區(qū)間為空）基于基本二分查找思路，設(shè)a[low..high]為當(dāng)前的查找區(qū)間，當(dāng)查找區(qū)間非空時(shí)求出mid=

(low+high)/2

，然后將k和a[mid]比較，分為3種情況：51/751 definsertpoint1(a,k): #查找第一個(gè)大于等于k的元素位置2 low,high=0,len(a)-13 whilelow<=high: #當(dāng)前區(qū)間至少有一個(gè)元素時(shí)4 mid=(low+high)//2 #求查找區(qū)間的中間位置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]不一定是第一個(gè)大于等于k的元素，繼續(xù)在左區(qū)間查找，但a[mid]可能是第一個(gè)等于k的元素，所以左區(qū)間應(yīng)該包含a[mid]，則新查找區(qū)間修改為a[low..mid]。若k<a[mid]，a[mid]不一定是第一個(gè)大于等于k的元素，繼續(xù)在左區(qū)間查找，但a[mid]可能是第一個(gè)大于k的元素，所以左區(qū)間應(yīng)該包含a[mid]，則新查找區(qū)間修改為a[low..mid]。若k>a[mid]，a[mid]一定不是第一個(gè)大于等于k的元素，繼續(xù)在右區(qū)間查找，則新查找區(qū)間修改為a[mid+1..high]。解法2（查找到區(qū)間僅含一個(gè)元素）a中k插入點(diǎn)的范圍是0～n，采用擴(kuò)展二分查找方法，若查找區(qū)間為a[low..high]（從a[0..n]開始），求出mid=(low+high)/2，元素比較分為3種情況：53/75問題描述：設(shè)計(jì)一個(gè)算法在所有相鄰元素值不相同的整數(shù)數(shù)組nums中（即對(duì)于所有有效的i都有nums[i]≠nums[i+1]）找峰值元素并返回其索引。

峰值元素是指其值大于左右相鄰值的元素。假設(shè)nums[-1]=nums[n]=-∞，如果包含多個(gè)峰值，返回任何一個(gè)峰值索引即可。

例如，nums[0..6]={1，2，1，3，5，6，4}，結(jié)果是1或5。

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

def

findPeakElement(self,

nums)

->

int12135644.3.4實(shí)戰(zhàn)—尋找峰值（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（查找到區(qū)間為空）55/75a[mid]>a[mid+1]a[low]<…<峰值

>…>a[mid]>a[mid+1]>…>a[high]在[0，n-1]中查找第一個(gè)滿足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:

#查找區(qū)間至少有一個(gè)元素時(shí)循環(huán)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上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為28ms，消耗空間為15MB。57/75解法2（查找到區(qū)間僅含一個(gè)元素)a中k插入點(diǎn)的范圍是0～n，設(shè)a[low..high]為當(dāng)前的查找區(qū)間（初始化為[0，n]。循環(huán)結(jié)束查找到區(qū)間含一個(gè)元素，就是答案。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:

#查找區(qū)間至少有兩個(gè)元素時(shí)循環(huán)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上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為32ms，消耗空間為15.1MB。59/75問題描述：對(duì)于一個(gè)長(zhǎng)度為n的有序序列（假設(shè)均為遞增序列）a[0..n-1]，處于中間位置的元素稱為a的中位數(shù)（當(dāng)n為奇數(shù)時(shí)中位數(shù)是唯一的，當(dāng)n為偶數(shù)時(shí)有兩個(gè)中位數(shù)，這里指前一個(gè)中位數(shù)）。

例如，若序列a=（11，13，15，17，19），其中位數(shù)是15。若b=（2，4，6，8，20），其中位數(shù)為6。

兩個(gè)等長(zhǎng)有序序列的中位數(shù)是含它們所有元素的有序序列的中位數(shù)，例如a、b兩個(gè)有序序列的中位數(shù)為11。設(shè)計(jì)一個(gè)算法求給定的兩個(gè)有序序列的中位數(shù)。4.3.5查找兩個(gè)等長(zhǎng)有序序列的中位數(shù)60/75采用二分法求含有n個(gè)有序元素的序列a、b的中位數(shù)855（1）若n=1，較小者為中位數(shù)。解61/75（2）n>1分為3種情況。分別求出a、b的中位數(shù)a[m1]和b[m2]：①若a[m1]=b[m2]，則a[m1]或b[m2]即為所求中位數(shù)，算法結(jié)束。1，3，5，6，92，3，5，8，10562/75②若a[m1]<b[m2]，則舍棄序列a中前半部分（較小的一半），同時(shí)舍棄序列b中后半部分（較大的一半）要求舍棄的長(zhǎng)度相等。1，3，4，6，92，3，5，8，104，6，92，3，54繼續(xù)求63/75③若a[m1]>b[m2]，則舍棄序列a中后半部分（較大的一半），同時(shí)舍棄序列b中前半部分（較小的一半），要求舍棄的長(zhǎng)度相等。舍棄一半即

n/2

個(gè)元素。1，3，5，6，92，3，4，8，101,3,54，8，104繼續(xù)求64/751 defmidnum1(a,i,b,j,n): #求a[i]和b[j]開頭長(zhǎng)度為n的中位數(shù)2 ifn==1: #兩序列均只有一個(gè)元素時(shí)3 returnmin(a[i],b[j])4 else: #均含兩個(gè)及以上素時(shí)5 m1=i+(n-1)//2 #求a的中位數(shù)6 m2=j+(n-1)//2 #求b的中位數(shù)7 ifa[m1]==b[m2]:returna[m1] #兩中位數(shù)相等時(shí)8 newn=(n+1)//2 #每個(gè)序列保留的元素個(gè)數(shù)9 ifa[m1]<b[m2]: #當(dāng)a[m1]<b[m2]時(shí)10 returnmidnum1(a,i+n-newn,b,j,newn)

#a取后半部分,b取前半部分11 else: #當(dāng)a[m1]>b[m2]時(shí)12 returnmidnum1(a,i,b,j+n-newn,newn)

#a取前半部分,b取后半部分65/7514 defmidnum(a,b,n): #求兩個(gè)有序序列a和b的中位數(shù)15 returnmidnum1(a,0,b,0,n)T(n)=1 當(dāng)n=1T(n)=T(n/2)+1

當(dāng)n>1容易推出，T(n)=O(log2n)。66/75問題描述：共有n（n>3）個(gè)硬幣，編號(hào)為0～n-1，其中有且僅有一個(gè)假幣，假幣與真幣的外觀相同但重量不同，事先知道假幣的重量比真幣輕。

現(xiàn)在用一架天平稱重，天平稱重的硬幣數(shù)沒有限制。設(shè)計(jì)一個(gè)算法找出這個(gè)假幣，使得稱重的次數(shù)最少。4.3.6查找假幣問題67/75采用三分查找思想。用c[0..n-1]存放n個(gè)硬幣，其中c[i]表示編號(hào)i的硬幣重量（真幣重量為2，假幣重量為1）。算法返回找到的假幣編號(hào)。解68/75n=1或者n=2直接求解。當(dāng)n≥3時(shí)查找假幣為原問題，將所有硬幣劃分為A、B和C三份，保證A、B中硬幣個(gè)數(shù)相同并且A和C中的硬幣個(gè)數(shù)最多相差1。將A和B稱重一次后轉(zhuǎn)換為在A、B或者C中查找假幣，對(duì)應(yīng)子問題的規(guī)模大約為n/3。簡(jiǎn)單地說，問題規(guī)模為n的原問題，通過一次稱重后，要么找到了假幣，要么轉(zhuǎn)換為一個(gè)問題規(guī)模大約為n/3的子問題，相當(dāng)于求解問題規(guī)模每次減少為n/3。查找假幣的過程如下：69/75202112232425262728ABC202112A1B1C112n=9，9個(gè)硬幣編號(hào)為0～8，假設(shè)硬幣重2，其中coins[2]=1。0～80～23～56～80～01～12～2示例70/751 defBalance(c,ia,ib,n): #c[ia]和c[ib]開始的n個(gè)硬幣稱重一次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個(gè))找假幣12 ifn==1:returni #剩余1個(gè)硬幣coins[i]13 elifn==2: #剩余硬幣coins[i]和coins[i+1]14 b=Balance(coins,i,i+1,1) #2個(gè)硬幣稱重15 ifb==1:returni #coins[i]是假幣16 else:returni+1 #coins[i+1]是假幣72/7517 else: #剩余3個(gè)或者以上硬幣18 k=0 #k為A和B中的硬幣個(gè)數(shù)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,個(gè)數(shù)分別為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個(gè)硬幣中假幣時(shí)的稱重次數(shù)，設(shè)為C(n)。假設(shè)n=3k，n=1時(shí)稱重0次，當(dāng)n=3時(shí)稱重1次，n=9時(shí)最多稱重次數(shù)為2，對(duì)應(yīng)的遞推式如下：C(n)=1 當(dāng)n=3時(shí)C(n)=C(n/3)+1 當(dāng)n>3時(shí)

可以推出C(n)=log3n。當(dāng)n≠3k時(shí)，由于A、B和C中硬幣個(gè)數(shù)最多相差1，所以最多稱重次數(shù)C(n)=

log3n

。例如，n=8時(shí)，n%3=2，劃分為（3，3，2），稱重1次后最壞情況的子問題是n1=3，該子問題稱重1次即可，所以總稱重次數(shù)為

log38

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

…

ai

…

amidamid+1

…

aj

…

ahighmaxLeftSummaxRightSum（a）遞歸求出maxLeftSum和maxRightSummax3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)（c）求出a序列中最大連續(xù)子序列的和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為中心的最大連續(xù)子序列和為20（c）結(jié)果=max3(11，13，20)=20示例79/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ù)子序列之和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序列中最大連續(xù)子序列和17 returnmaxSubSum51(a,0,len(a)-1)82/33T(n)=1 當(dāng)n=1T(n)=2T(n/2)+n

當(dāng)n>1T(n)=O(nlog2n)算法分析83/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，對(duì)應(yīng)的連續(xù)子數(shù)組是{4，-1，2，1}。

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

def

maxSubArray(self,

nums:

List[int])

->

int4.4.2實(shí)戰(zhàn)—最大子序列和（LeetCode53★）84/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部分的最大值。解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]

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

mid=(low+high)//2

#求中間位置10

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

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

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

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

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

n/2

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

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

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

def

majorityElement(self,

nums)

->

int:4.4.3實(shí)戰(zhàn)—多數(shù)元素（LeetCode169）90/33nums[0..n-1]中一定存在多數(shù)元素。當(dāng)n=1，nums[0]就是多數(shù)元素，否則針對(duì)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ù)元素。解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