Python程序員面試分類真題8

Python程序員面試分類真題81.

給定一個(gè)整數(shù)數(shù)組，如何快速地求出該數(shù)組中第k小的數(shù)。假如數(shù)組為[4,0,1,0,2,3]，那么第3小的元素是1。正確答案：由于對(duì)一個(gè)有序的數(shù)組而言，能非常容易地（江南博哥）找到數(shù)組中第k小的數(shù)，因此，可以通過(guò)對(duì)數(shù)組進(jìn)行排序的方法來(lái)找出第k小的數(shù)。同時(shí)，由于只要求第k小的數(shù)，因此，沒有必要對(duì)數(shù)組進(jìn)行完全排序，只需要對(duì)數(shù)組進(jìn)行局部排序就可以了。下面分別介紹這幾種不同的實(shí)現(xiàn)方法。

方法一：排序法

最簡(jiǎn)單的方法就是首先對(duì)數(shù)組進(jìn)行排序，在排序后的數(shù)組中，下標(biāo)為k-1的值就是第k小的數(shù)。例如：對(duì)數(shù)組[4,0,1,0,2,3]進(jìn)行排序后的序列變?yōu)閇0,0,1,2,3,4]，第3小的數(shù)就是排序后數(shù)組中下標(biāo)為2對(duì)應(yīng)的數(shù)：1。由于最高效的排序算法(例如快速排序)的平均時(shí)間復(fù)雜度為O(Nlog2N)，因此，此時(shí)該方法的平均時(shí)間復(fù)雜度為O(Nlog2N)，其中，N為數(shù)組的長(zhǎng)度。

方法二：部分排序法

由于只需要找出第k小的數(shù)，因此，沒必要對(duì)數(shù)組中所有的元素進(jìn)行排序，可以采用部分排序的方法。具體思路為：通過(guò)對(duì)選擇排序進(jìn)行改造，第一次遍歷從數(shù)組中找出最小的數(shù)，第二次遍歷從剩下的數(shù)中找出最小的數(shù)(在整個(gè)數(shù)組中是第二小的數(shù))，第k次遍歷就可以從N-k+1(N為數(shù)組的長(zhǎng)度)個(gè)數(shù)中找出最小的數(shù)(在整個(gè)數(shù)組中是第k小的)。這種方法的時(shí)間復(fù)雜度為O(N*k)。當(dāng)然也可以采用堆排序進(jìn)行k趟排序找出第k小的值。

方法三：類快速排序方法

快速排序的基本思想為：將數(shù)組array[low..high]中某一個(gè)元素(取第一個(gè)元素)作為劃分依據(jù)，然后把數(shù)組劃分為三部分：1)array[low...i-1](所有的元素的值都小于或等于array[i])、2)array[i]、3)array[i+1...high](所有的元素的值都大于array[i])。在此基礎(chǔ)上可以用下面的方法求出第k小的元素：

(1)如果i-low==k-1，說(shuō)明array[i]就是第k小的元素，那么直接返回array[i]；

(2)如果i-low>k-1，說(shuō)明第k小的元素肯定在array[low...i-1]中，那么只需要遞歸地在array[low...i-1]中找第k小的元素即可；

(3)如果i-low＜k-1，說(shuō)明第k小的元素肯定在array[i+1...high]中，那么只需要遞歸地在array[i+1...high]中找第k-(i-low)-1小的元素即可。

對(duì)于數(shù)組(4,0,1,0,2,3)，第一次劃分后，劃分為下面三部分：

(3,0,1,0,2),(4),()

接下來(lái)需要在(3,0,1,0,2)中找第3小的元素，把(3,0,1,0,2)劃分為三部分：

(2,0,1,0),(3),()

接下來(lái)需要在(2,0,1,0)中找第3小的元素，把(2,0,1,0)劃分為三部分：

(0,0,1),(2),()

接下來(lái)需要在(0,0,1)中找第3小的元素，把(0,0,1)劃分為三部分：

(0),(0),(1)

此時(shí)i=1,low=0;(i-1=1)＜(k-1=2)，接下來(lái)需要在(1)中找第k-(i-low)-1=1小的元素即可。顯然，(1)中第1小的元素就是1。

實(shí)現(xiàn)代碼如下：

"""

方法功能:在數(shù)組array中找出第k小的值

輸入?yún)?shù):array為整數(shù)數(shù)組,low為數(shù)組起始下標(biāo),high為數(shù)組右邊界的下標(biāo),k為整數(shù)

返回值:數(shù)組中第k小的值

"""

deffindSmallK(array,low,high,k):

i=low

j=high

splitElem=array[i]

#把小于等于splitElem的數(shù)放到數(shù)組中splitElem的左邊,大于splitElem的值放到右邊

whilei＜j:

whilei＜jandarray[j]＞=splitElem:

j-=1

ifi＜j:

array[i]=array[j]

i+=1

whilei＜jandarray[i]＜=splitElem:

i+=1

ifi＜j:

array[j]=array[i]

j-=1

array[i]=splitElem

#splitElem在子數(shù)組array[low～high]中下標(biāo)的偏移量

subArrayIndex=i-low

#splitElem在array[low～high]所在的位置恰好為k-1,那么它就是第k小的元素

ifsubArrayIndex==k-1:

returnarray[i]

#splitElem在array[low～high]所在的位置大于k-1,那么只需在array[low～i-1]中找第k小的元素

elifsubArrayIndex＞k-1:

returnfindSmallK(array,low,i-1,k)

#array[i+1～high]中找第k-i+low-1小的元素

else:

returnfindSmallK(array,i+1,high,k-(i-low)-1)

if__name__=="__main__":

k=3

array=[4,0,1,0,2,3]

print"第"+str(k)+"小的值為:"+str(findSmallK(array,0,len(array)-1,k))

程序的運(yùn)行結(jié)果為：

第3小的值為：1

算法性能分析：

快速排序的平均時(shí)間復(fù)雜度為O(Nlog2N)。快速排序需要對(duì)劃分后的所有子數(shù)組繼續(xù)排序處理，而本方法只需要取劃分后的其中一個(gè)子數(shù)組進(jìn)行處理即可，因此，平均時(shí)間復(fù)雜度肯定小于O(Nlog2N)。由此可以看出，這種方法的效率要高于方法一。但是這種方法也有缺點(diǎn)：它改變了數(shù)組中數(shù)據(jù)原來(lái)的順序。當(dāng)然可以申請(qǐng)額外的N(其中，N為數(shù)組的長(zhǎng)度)個(gè)空間來(lái)解決這個(gè)問(wèn)題，但是這樣做會(huì)增加算法的空間復(fù)雜度，所以，通常做法是根據(jù)實(shí)際情況選取合適的方法。[考點(diǎn)]如何找出數(shù)組中第k小的數(shù)

2.

給定一個(gè)數(shù)組，數(shù)組中含有重復(fù)元素，給定兩個(gè)數(shù)字num1和num2，求這兩個(gè)數(shù)字在數(shù)組中出現(xiàn)的位置的最小距離。正確答案：對(duì)于這類問(wèn)題，最簡(jiǎn)單的方法就是對(duì)數(shù)組進(jìn)行雙重遍歷，找出最小距離，但是這種方法效率比較低下。由于在求距離的時(shí)候只關(guān)心num1與num2這兩個(gè)數(shù)，因此，只需要對(duì)數(shù)組進(jìn)行一次遍歷即可，在遍歷的過(guò)程中分別記錄遍歷到num1或num2的位置就可以非常方便地求出最小距離，下面分別詳細(xì)介紹這兩種實(shí)現(xiàn)方法。

方法一：蠻力法

主要思路為：對(duì)數(shù)組進(jìn)行雙重遍歷，外層循環(huán)遍歷查找num1，只要遍歷到num1，內(nèi)層循環(huán)對(duì)數(shù)組從頭開始遍歷找num2，每當(dāng)遍歷到num2，就計(jì)算它們的距離dist。當(dāng)遍歷結(jié)束后最小的dist值就是它們最小的距離。實(shí)現(xiàn)代碼如下：

defminDistance(arr,num1,num2):

ifarr==Noneorlen(arr)＜=0:

print"參數(shù)不合理"

return2**32

minDis=2**32#num1與num2的最小距離

dist0

i=0

whilei＜len(arr):

ifarr[i]==num1:

j=0

whilej＜len(arr):

ifarr[j]==num2:

dist=abs(i-j)#當(dāng)前遍歷的num1與num2的距離

ifdist＜minDis:

minDis=dist

j+=1

i+=1

returnminDis

if__name__="__main__":

arr=[4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8]

num1=4

num2=8

printminDistance(arr,num1,num2)

程序的運(yùn)行結(jié)果為：

2

算法性能分析：

這種方法需要對(duì)數(shù)組進(jìn)行兩次遍歷，因此，時(shí)間復(fù)雜度為O(n2)。

方法二：動(dòng)態(tài)規(guī)劃

上述方法的內(nèi)層循環(huán)對(duì)num2的位置進(jìn)行了很多次重復(fù)的查找?？梢圆捎脛?dòng)態(tài)規(guī)劃的方法把每次遍歷的結(jié)果都記錄下來(lái)從而減少遍歷次數(shù)。具體實(shí)現(xiàn)思路為：遍歷數(shù)組，會(huì)遇到以下兩種情況：

(1)當(dāng)遇到num1時(shí)，記錄下num1值對(duì)應(yīng)的數(shù)組下標(biāo)的位置lastPos1，通過(guò)求lastPos1與上次遍歷到num2下標(biāo)的位置的值lastPos2的差可以求出最近一次遍歷到的num1與num2的距離。

(2)當(dāng)遇到num2時(shí)，同樣記錄下它在數(shù)組中下標(biāo)的位置lastPos2，然后通過(guò)求lastPos2與上次遍歷到num1的下標(biāo)值lastPos1，求出最近一次遍歷到的num1與num2的距離。

假設(shè)給定數(shù)組為：[4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8],num1=4,num2=8。根據(jù)以上方法，執(zhí)行過(guò)程如下：

1)在遍歷的時(shí)候首先會(huì)遍歷到4，下標(biāo)為lastPos1=0，由于此時(shí)還沒有遍歷到num2，因此，沒必要計(jì)算num1與num2的最小距離；

2)接著往下遍歷，又遍歷到num1=4，更新lastPos1=3；

3)接著往下遍歷，又遍歷到num1=4，更新lastPos1=7；

4)接著往下遍歷，又遍歷到num2=8，更新lastPos2=9；此時(shí)由于前面已經(jīng)遍歷到過(guò)num1，因此，可以求出當(dāng)前num1與num2的最小距離為|lastPos2-lastPos1|=2；

5)接著往下遍歷，又遍歷到num2=8，更新lastPos2=15；此時(shí)由于前面已經(jīng)遍歷到過(guò)num1，因此，可以求出當(dāng)前num1與num2的最小距離為|lastPos2-lastPos1|=8；由于8＞2，所以，num1與num2的最小距離為2。

實(shí)現(xiàn)代碼如下：

defminDistance(arr,num1,num2):

ifarr==Noneorlen(arr)＜=0:

print"參數(shù)不合理"

return2**32

lastPos1=-l#上次遍歷到num1的位置

lastPos2=-1#上次遍歷到num2的位置

minDis=2**30#num1與num2的最小距離

i=0

whilei＜len(arr):

ifarr[i]==num1:

lastPos1=i

iflastPos2＞=0:

minDis=min(minDis,lastPos1-lastPos2)

ifarr[i]==num2:

IastPos2=i

iflastPos1＞=0:

minDis=min(minDis,lastPos2-lastPos1)

i+=1

returnminDis

if__name__=="__main__":

arr=[4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8]

num1=4

num2=8

printminDistance(arr,num1,num2)

算法性能分析：

這種方法只需要對(duì)數(shù)組進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(N)。[考點(diǎn)]如何求數(shù)組中兩個(gè)元素的最小距離

3.

已知三個(gè)升序整數(shù)數(shù)組a[1],b[m]和c[n]，請(qǐng)?jiān)谌齻€(gè)數(shù)組中各找一個(gè)元素，使得組成的三元組距離最小。三元組距離的定義是：假設(shè)a[i]、b[j]和c[k]是一個(gè)三元組，那么距離為：Distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)求最小三元組距離的最優(yōu)算法。正確答案：最簡(jiǎn)單的方法就是找出所有可能的組合，從所有的組合中找出最小的距離，但是顯然這種方法的效率比較低下。通過(guò)分析發(fā)現(xiàn)，當(dāng)ai≤bi≤ci時(shí)，此時(shí)它們的距離肯定為Di=ci-ai。此時(shí)就沒必要求bi-ai與ci-ai的值了，從而可以省去很多沒必要的步驟，下面分別詳細(xì)介紹這兩種方法。

方法一：蠻力法

最容易想到的方法就是分別遍歷三個(gè)數(shù)組中的元素，對(duì)遍歷到的元素分別求出它們的距離，然后從這些值里面查找最小值，實(shí)現(xiàn)代碼如下：

defmaxs(a,b,c):

maxs=bifa＜belsea

maxs=cifmaxs＜celsemaxs

returnmaxs

defminDistance(a,b,c):

aLen=len(a)

bLen=len(b)

cLen=len(c)

minDist=maxs(abs(a[0]-b[0]),abs(a[0]-c[0]),abs(b[0]-c[0]))

dist=0

i=0

whilei＜aLen:

j=0

whilej＜bLen:

k=0

whilek＜cLen:

#求距離

dist=maxs(abs(a[i]-b[j]),abs(a[i]-c[k]).abs(b[j]-c[k]))

#找到最小距離

ifminDist＞dist:

minDist=dist

k+=1

j+=1

i+=1

returnminDist

if__name__=="__main__":

a=[3,4,5,7,15]

b=[10,12,14,16,17]

c=[20,21,23,24,37,30]

print"最小離為:"+str(minDistance(a,b,c))

程序的運(yùn)行結(jié)果為：

最小距離為：5

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(l*m*n)，顯然這種方法沒有用到數(shù)組升序這一特性，因此，該方法肯定不是最好的方法。

方法二：最小距離法

假設(shè)當(dāng)前遍歷到這三個(gè)數(shù)組中的元素分別為ai，bi，ci，并且ai≤bi≤ci，此時(shí)它們的距離肯定為Di=ci-ai，那么接下來(lái)可以分如下三種情況討論：

(1)如果接下來(lái)求ai，bi，ci+1的距離，由于ci+1≥ci，此時(shí)它們的距離必定為Di+1=ci+1-ai，顯然Di+1≥Di，因此，Di+1不可能為最小距離。

(2)如果接下來(lái)求ai，bi+1，ci的距離，由于bi+1≥bi，如果bi+1≤ci，此時(shí)它們的距離仍然為Di+1=ci-ai；如果bi+1＞ci，那么此時(shí)它們的距離為Di+1=bi+1-ai，顯然Di+1≥Di，因此，Di+1不可能為最小距離。

(3)如果接下來(lái)求ai+1，bi，ci的距離，如果ai+1＜ci-|ci-ai|，此時(shí)它們的距離Di+1=max(ci-ai+1，ci-bi)，顯然Di+1＜Di，因此，Di+1有可能是最小距離。

綜上所述，在求最小距離的時(shí)候只需要考慮第3種情況即可。具體實(shí)現(xiàn)思路為：從三個(gè)數(shù)組的第一個(gè)元素開始，首先求出它們的距離minDist，接著找出這三個(gè)數(shù)中最小數(shù)所在的數(shù)組，只對(duì)這個(gè)數(shù)組的下標(biāo)往后移一個(gè)位置，接著求三個(gè)數(shù)組中當(dāng)前遍歷元素的距離，如果比minDist小，則把當(dāng)前距離賦值給minDist，依此類推，直到遍歷完其中一個(gè)數(shù)組為止。

例如給定數(shù)組：a=[3,4,5,7,15];b=[10,12,14,16,17];c=[20,21,23,24,37,30];

1)首先從三個(gè)數(shù)組中找出第一個(gè)元素3,10,20，顯然它們的距離為20-3=17；

2)由于3最小，因此，數(shù)組a往后移一個(gè)位置，求4,10,20的距離為16，由于16＜17，因此，當(dāng)前數(shù)組的最小距離為16；

3)同理，對(duì)數(shù)組a后移一個(gè)位置，依次類推直到遍歷到15的時(shí)候，當(dāng)前遍歷到三個(gè)數(shù)組中的值分別為15,10,20，最小距離為10；

4)由于10最小，因此，數(shù)組b往后移動(dòng)一個(gè)位置遍歷12，此時(shí)三個(gè)數(shù)組遍歷到的數(shù)字分別為15,12,20，距離為8，當(dāng)前最小距離是8；

5)由于8最小，數(shù)組b往后移動(dòng)一個(gè)位置為14，依然是三個(gè)數(shù)中最小值，往后移動(dòng)一個(gè)位置為16，當(dāng)前的最小距離變?yōu)?，由于15是數(shù)組a的最后一個(gè)數(shù)字，因此，遍歷結(jié)束，求得最小距離為5。

實(shí)現(xiàn)代碼如下：

defmins(a,b,c):

mins=aifa＜belseb

mins=minsifmins＜celsec

returnmins

defmaxs(a,b,c):

maxs=bifa＜belsea

maxs=cifmaxs＜celsemaxs

returnmaxs

defminDistance(a,b,c):

aLen=len(a)

bLen=len(b)

cLen=len(c)

curDist=0

minsd=0

minDist=2**32

i=0#數(shù)組a的下標(biāo)

j=0#數(shù)組b的下標(biāo)

k=0#數(shù)組c的下標(biāo)

whileTrue:

curDist=maxs(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))

ifcurDist＜minDist:

minDist=curDist

#找出當(dāng)前遍歷到三個(gè)數(shù)組中的最小值

minsd=mins(a[i],b[j],c[k])

ifminsd=a[i]:

i+=1

ifi＞=aLen:

break

elifminsd==b[j]:

j+=1

ifj＞=bLen:

break

else:

k+=1

ifk＞=cLen:

break

returnminDist

if__name__=="__main__":

a=[3,4,5,7,15]

b=[10,12,14,16,17]

c=[20,21,23,24,37,30]

print"最小距離為:"+str(minDistance(a,b,c))

算法性能分析：

采用這種算法最多只需要對(duì)三個(gè)數(shù)組分別遍歷一遍，因此，時(shí)間復(fù)雜度為O(1+n1+n)。

方法三：數(shù)學(xué)運(yùn)算法

采用數(shù)學(xué)方法對(duì)目標(biāo)函數(shù)變形，有兩個(gè)關(guān)鍵點(diǎn)，第一個(gè)關(guān)鍵點(diǎn)：

max{|x1-x2|,|y1-y2|}=(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2(公式1)

我們假設(shè)x1=a[i]，x2=b[j]，x3=c[k]，則

Distance=max(|x1-x2|,|x1-x3|,|x2-x3|)=max(max(|x1-x2|,|x1-x3|),|x2-x3|)(公式2)

根據(jù)公式1，max(|x1-x2|，|x1-x3|)=1/2(|2x1-x2-x3|+|x2-x3|)，帶入公式2，得到

Distance=max(1/2(|2x1-x2-x3|+|x2-x3|),|x2-x3|)=1/2*max(|2×1-x2-x3|,|x2-x3|)+1/2*|x2-x3|//把相同部分1/2*|x2-x3|分離出來(lái)

=1/2*max(|2x1-(x2+x3)|,|x2-x3|)+1/2*|x2-x3|//把(x2+x3)看成一個(gè)整體，使用公式1

=1/2*1/2*((|2x1-2x2|+|2x1-2x3|)+1/2*|x2-x3|

=1/2*|x1-x2|+1/2*|x1-x3|+1/2*|x2-x3|

=1/2*(|x1-x2|+|x1-x3|+|x2-x3|)//求出等價(jià)公式，完畢!

第二個(gè)關(guān)鍵點(diǎn)：如何設(shè)計(jì)算法找到(|x1-x2|+|x1-x3|+|x2-x3|)的最小值，x1，x2，x3，分別是三個(gè)數(shù)組中的任意一個(gè)數(shù)，算法思想與方法二相同，用三個(gè)下標(biāo)分別指向a，b，c中最小的數(shù)，計(jì)算一次它們最大距離的Distance，然后再移動(dòng)三個(gè)數(shù)中較小的數(shù)組的下標(biāo)，再計(jì)算一次，每次移動(dòng)一個(gè)，直到其中一個(gè)數(shù)組結(jié)束為止。

示例代碼如下：

defmins(a,b,c):

mins=aifa＜belseb

mins=minsifmins＜celsec

returnmins

defminDistance(a,b,c):

aLen=len(a)

bLen=len(b)

cLen=len(c)

MinSum=0#最小的絕對(duì)值和

Sum=0#計(jì)算三個(gè)絕對(duì)值的和,與最小值做比較

MinOFabc=0#a[i],b[j],c[k]的最小值

cnt=0#循環(huán)次數(shù)統(tǒng)計(jì),最多是1+m+n次i=0,j=0,k=0//a,b,c三個(gè)數(shù)組的下標(biāo)索引

i=j=k=0

MinSum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2

cnt=0

whilecnt＜=aLen+bLen+cLen:

Sum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2

MinSum=MinSumifMinSum＜SumelseSum

MinOFabc=mins(a[i],b[j],c[k])#找到a[i],b[j],c[k]的最小值

#判斷哪個(gè)是最小值,做相應(yīng)的索引移動(dòng)

ifMinOFabc==a[i]:

i+=1

ifi＞=aLen:

break#a[i]最小,移動(dòng)i

ifMinOFabc==b[j]:

j+=1

ifj＞=bLen:

break#b[j]最小,移動(dòng)j

ifMinOFabc==c[k]:

k+=1

ifk＞=cLen:

break#c[k]最小,移動(dòng)k

cnt+=1

returnMinSum

if__name__=="__main__":

a=[3,4,5,7,15]

b=[10,12,14,16,17]

c=[20,21,23,24,37,30]

print"最小距離為:"+str(minDistance(a,b,c))

程序的運(yùn)行結(jié)果為：

最小距離為：5

算法性能分析：

與方法二類似，這種方法最多需要執(zhí)行(1+m+n)次循環(huán)，因此，時(shí)間復(fù)雜度為O(1+m+n)。[考點(diǎn)]如何求解最小三元組距離

4.

有一個(gè)升序排列的數(shù)組，數(shù)組中可能有正數(shù)、負(fù)數(shù)或0，求數(shù)組中元素的絕對(duì)值最小的數(shù)。例如，數(shù)組[-10，-5，-2，7，15，50]，該數(shù)組中絕對(duì)值最小的數(shù)是-2。正確答案：可以對(duì)數(shù)組進(jìn)行順序遍歷，對(duì)每個(gè)遍歷到的數(shù)求絕對(duì)值進(jìn)行比較就可以很容易地找出數(shù)組中絕對(duì)值最小的數(shù)。本題中，由于數(shù)組是升序排列的，那么絕對(duì)值最小的數(shù)一定在正數(shù)與非正數(shù)的分界點(diǎn)處，利用這種方法可以省去很多求絕對(duì)值的操作。下面分別詳細(xì)介紹這幾種方法。

方法一：順序比較法

最簡(jiǎn)單的方法就是從頭到尾遍歷數(shù)組元素，對(duì)每個(gè)數(shù)字求絕對(duì)值，然后通過(guò)比較就可以找出絕對(duì)值最小的數(shù)。

以數(shù)組[-10，-5，-2，7，15，50]為例，實(shí)現(xiàn)方式如下：

(1)首先遍歷第一個(gè)元素-10，其絕對(duì)值為10，所以，當(dāng)前最小值為min=10；

(2)遍歷第二個(gè)元素-5，其絕對(duì)值為5，由于5＜10，因此，當(dāng)前最小值min=5；

(3)遍歷第三個(gè)元素-2，其絕對(duì)值為2，由于2＜5，因此，當(dāng)前最小值為min=2；

(4)遍歷第四個(gè)元素7，其絕對(duì)值為7，由于7＞2，因此，當(dāng)前最小值min還是2；

(5)依此類推，直到遍歷完數(shù)組為止，就可以找出絕對(duì)值最小的數(shù)為-2。

示例代碼如下：

deffindMin(array):

ifarray==Noneorlen(array)＜=0:

print"輸入?yún)?shù)不合理"

return0

mins=2**32

i=0

whilei＜len(array):

ifabs(array[i])＜abs(mins):

mins=array[i]

i+=1

returnmins

if__name__=="__main__":

arr=[-10,-5,-2,7,15,50]

print"絕對(duì)值最小的數(shù)為:"+str(findMin(arr))

程序的運(yùn)行結(jié)果為：

絕對(duì)值最小的數(shù)為：-2

算法性能分析：

該方法的平均時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。

方法二、二分法

在求絕對(duì)值最小的數(shù)時(shí)可以分為如下三種情況：1)如果數(shù)組第一個(gè)元素為非負(fù)數(shù)，那么絕對(duì)值最小的數(shù)肯定為數(shù)組第一個(gè)元素；2)如果數(shù)組最后一個(gè)元素的值為負(fù)數(shù)，那么絕對(duì)值最小的數(shù)肯定是數(shù)組的最后一個(gè)元素；3)如果數(shù)組中既有正數(shù)又有負(fù)數(shù)，首先找到正數(shù)與負(fù)數(shù)的分界點(diǎn)，如果分界點(diǎn)恰好為0，那么0就是絕對(duì)值最小的數(shù)。否則通過(guò)比較分界點(diǎn)左右的正數(shù)與負(fù)數(shù)的絕對(duì)值來(lái)確定最小的數(shù)。

那么如何來(lái)查找正數(shù)與負(fù)數(shù)的分界點(diǎn)呢?最簡(jiǎn)單的方法仍然是順序遍歷數(shù)組，找出第一個(gè)非負(fù)數(shù)(前提是數(shù)組中既有正數(shù)又有負(fù)數(shù))，接著通過(guò)比較分界點(diǎn)左右兩個(gè)數(shù)的值來(lái)找出絕對(duì)值最小的數(shù)。這種方法在最壞的情況下時(shí)間復(fù)雜度為O(N)。下面主要介紹采用二分法來(lái)查找正數(shù)與負(fù)數(shù)的分界點(diǎn)的方法。主要思路為：取數(shù)組中間位置的值a[mid]，并將它與0值比較，比較結(jié)果分為以下3種情況：

(1)如果a[mid]=0，那么這個(gè)數(shù)就是絕對(duì)值最小的數(shù)；

(2)如果a[mid]＞0，a[mid-1]＜0，那么就找到了分界點(diǎn)，通過(guò)比較a[mid]與a[mid-1]的絕對(duì)值就可以找到數(shù)組中絕對(duì)值最小的數(shù)；如果a[mid-1]==0，那么a[mid-1]就是要找的數(shù)；否則接著在數(shù)組的左半部分查找；

(3)如果a[mid]＜0，a[mid+1]＞0，那么通過(guò)比較a[mid]與a[mid+1]的絕對(duì)值即可；如果a[mid+1]=0，那么a[mid+1]就是要查找的數(shù)。否則接著在數(shù)組的右半部分繼續(xù)查找。

為了更好地說(shuō)明以上方法，可以參考以下幾個(gè)示例進(jìn)行分析：

(1)如果數(shù)組為[1,2,3,4,5,6,7]，由于數(shù)組元素全部為正數(shù)，而且數(shù)組是升序排列，所以，此時(shí)絕對(duì)值最小的元素為數(shù)組的第一個(gè)元素1。

(2)如果數(shù)組為[-7,-6,-5,-4,-3,-2,-1]，此時(shí)數(shù)組長(zhǎng)度length的值為7，由于數(shù)組元素全部為負(fù)數(shù)，而且數(shù)組是升序排列，所以，此時(shí)絕對(duì)值最小的元素為數(shù)組的第length-1個(gè)元素，該元素的絕對(duì)值為1。

(3)如果數(shù)組為[-7,-6,-5,-3,-1,2,4]，此時(shí)數(shù)組長(zhǎng)度length為7，數(shù)組中既有正數(shù)，也有負(fù)數(shù)，此時(shí)采用二分查找法，判斷數(shù)組中間元素的符號(hào)。中間元素的值為-3，小于0，所以，判斷中間元素后面一個(gè)元素的符號(hào)，中間元素后面的元素的值為-1小于0，因此，絕對(duì)值最小的元素一定位于右半部份數(shù)組[-1,2,4]中，繼續(xù)在右半部分?jǐn)?shù)組中查找，中間元素為2大于0，2前面一個(gè)元素的值為-1小于0，所以，-1與2中絕對(duì)值最小的元素即為所求的數(shù)組的絕對(duì)值最小的元素的值，所以，數(shù)組中絕對(duì)值最小的元素的值為-1。

實(shí)現(xiàn)代碼如下：

deffindMin(array):

ifarray==Noneorlen(array)＜=0:

print"輸入?yún)?shù)不合理";

return0;

lens=len(array)

#數(shù)組中沒有負(fù)數(shù)

ifarray[0]＞=0:

returnarray[0];

#數(shù)組中沒有正數(shù)

ifarray[lens-1]＜=0:

returnarray[lens-1];

mid=0;

begin=0;

end=lens-1;

absMin=0;

#數(shù)組中既有正數(shù)又有負(fù)數(shù)

whileTrue:

mid=begin+(end-begin)/2;

#如果等于0,那么就是絕對(duì)值最小的數(shù)

ifarray[mid]==0:

return0;#如果大于0,正負(fù)數(shù)的分界點(diǎn)在左側(cè)

elifarray[mid]＞0:

#繼續(xù)在數(shù)組的左半部分查找

ifarray[mid-1]＞O:

end=mid-1;

elifarray[mid-1]==0:

return0;

#找到正負(fù)數(shù)的分界點(diǎn)

else:

break;#如果小于0,在數(shù)組右半部分查找

else:

#在數(shù)組右半部分繼續(xù)查找

ifarray[mid+1]＜0:

begin=mid+1

elifarray[mid+1]==O:

return0;

#找到正負(fù)數(shù)的分界點(diǎn)

else:

break;

#獲取正負(fù)數(shù)分界點(diǎn)處絕對(duì)值最小的值

if(array[mid]＞0):

ifarray[mid]＜abs(array[mid-1]):

absMin=array[mid];

else:

absMin=array[mid-1];

else:

ifabs(array[mid])＜array[mid+1]:

absMin=array[mid];

else:

absMin=array[mid+1];

returnabsMin;

if__name__="__main__":

arr=[-10,-5,-2,7,15,50]

print"絕Xt值最小的數(shù)為:"+str(findMin(arr))

算法性能分析：

通過(guò)上面的分析可知，由于采取了二分查找的方式，算法的平均時(shí)間復(fù)雜度得到了大幅降低，為O(log2N)，其中，N為數(shù)組的長(zhǎng)度。[考點(diǎn)]如何求數(shù)組中絕對(duì)值最小的數(shù)

5.

一個(gè)有n個(gè)元素的數(shù)組，這n個(gè)元素既可以是正數(shù)也可以是負(fù)數(shù)，數(shù)組中連續(xù)的一個(gè)或多個(gè)元素可以組成一個(gè)連續(xù)的子數(shù)組，一個(gè)數(shù)組可能有多個(gè)這種連續(xù)的子數(shù)組，求子數(shù)組和的最大值。例如：對(duì)于數(shù)組[1，-2，4，8，-4，7，-1，-5]而言，其最大和的子數(shù)組為[4，8，-4，7]，最大值為15。正確答案：這是一道非常經(jīng)典的在筆試面試中碰到的算法題，有多種解決方法，下面分別從簡(jiǎn)單到復(fù)雜逐個(gè)介紹各種方法。

方法一：蠻力法

最簡(jiǎn)單也是最容易想到的方法就是找出所有的子數(shù)組，然后求出子數(shù)組的和，在所有子數(shù)組的和中取最大值。實(shí)現(xiàn)代碼如下：

defmaxSubArray(arr):

ifarr==Noneorlen(arr)＜1:

print"參數(shù)不合法"

return

ThisSum=0

MaxSum=0

i=0

whilei＜len(arr):

j=i

whilej＜len(arr):

ThisSum=0

k=i

whilek＜j:

ThisSum+=arr[k]

k+=1

ifThisSum＞MaxSum:

MaxSum=ThisSum

j+=1

i+=1

returnMaxSum

if__name_=="_main_":

arr=[1,-2,4,8,-4,7,-1,-5]

print"連續(xù)最大和為:"+str(maxSubArray(arr))

程序的運(yùn)行結(jié)果為：

連續(xù)最大和為：15

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(n3)，顯然效率太低，通過(guò)對(duì)該方法進(jìn)行分析發(fā)現(xiàn)，許多子數(shù)組都重復(fù)計(jì)算了，鑒于此，下面給出一種優(yōu)化的方法。

方法二：重復(fù)利用已經(jīng)計(jì)算的子數(shù)組和

由于Sum[i,j]=Sum[i,j-1]+arr[j]，在計(jì)算Sum[i,j]的時(shí)候可以使用前面已計(jì)算出的Sum[i,j-1]而不需要重新計(jì)算，采用這種方法可以省去計(jì)算Sum[i,j-1]的時(shí)間，因此，可以提高程序的效率。

實(shí)現(xiàn)代碼如下：

defmaxSubArray(arr):

ifarr==Noneorlen(arr)＜1:

print"參數(shù)不合法"

return

maxSum=-2**31

i=0

whilei＜len(arr):

sums=0

j=i

whilej＜len(arr):

sums+=arr[j]

ifsums＞maxSum:

maxSum=sums

j+=1

i+=1

returnmaxSum

if__name__=="__m