Python程序員面試分類真題7

Python程序員面試分類真題7(總分：100.00，做題時(shí)間：90分鐘)面試題(總題數(shù)：5，分?jǐn)?shù)：100.00)1.

數(shù)字1～1000放在含有1001個(gè)元素的數(shù)組中，其中只有唯一的一個(gè)元素值重復(fù)，其他數(shù)字均只出現(xiàn)一次。設(shè)計(jì)一個(gè)算法，將重復(fù)元素找出來(lái)，要求每個(gè)數(shù)組元素只能訪問(wèn)一次。如果不使用輔助存儲(chǔ)空間，能否設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)?

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(方法一：空間換時(shí)間法

拿到題目，首先需要做的就是分析題目所要達(dá)到的目標(biāo)以及其中的限定條件。從題目的描述中可以發(fā)現(xiàn)，本題的目標(biāo)就是在一個(gè)有且僅有一個(gè)元素值重復(fù)的數(shù)組中找出這個(gè)唯一的重復(fù)元素，而限定條件就是每個(gè)數(shù)組元素只能訪問(wèn)一次，并且不許使用輔助存儲(chǔ)空間。很顯然，從前面對(duì)Hash法的分析中可知，如果題目沒(méi)有對(duì)是否可以使用輔助數(shù)組做限制的話，最簡(jiǎn)單的方法就是使用Hash法。而在Python中可以使用字典來(lái)替代Hash法的功能。

當(dāng)使用字典時(shí)，具體過(guò)程如下所示：首先定義一個(gè)字典，將字典中的元素值(key值)都初始化為0，將原數(shù)組中的元素逐一映射到該字典的key中，當(dāng)對(duì)應(yīng)的key中的value值為0時(shí)，則置該key的value值為1，當(dāng)對(duì)應(yīng)的key的value值為1時(shí)，則表明該位置的數(shù)在原數(shù)組中是重復(fù)的，輸出即可。

示例代碼如下：

"""

方法功能:在數(shù)組中找唯一重復(fù)的元素

輸入?yún)?shù):array:數(shù)組對(duì)象的引用

返回值:重復(fù)元素的值,如果無(wú)重復(fù)元素則返回-1

"""

#使用字典

deffindDup(array):

ifNone==array:

return-1

lens=len(array)

hashTable=dict()

i=0

whilei＜lens-1:

hashTable[i]=0

i+=1

j=0

whilej＜lens:

ifhashTable[array[j]-1]==0:

hashTable[array[j]-1]=array[j]-1

else:

returnarray[i]

j+=1

return-1

if__name__="__main__":

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

printfindDup(array)

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

3

算法性能分析：

上述方法是一種典型的以空間換時(shí)間的方法，它的時(shí)間復(fù)雜度為O(N)，空問(wèn)復(fù)雜度為O(N)，很顯然，在題目沒(méi)有明確限制的情況下，上述方法不失為一種好方法，但是，由于題目要求不能用額外的輔助空間，所以，上述方法不可取，是否存在其他滿足題意的方法呢?

方法二：累加求和法

計(jì)算機(jī)技術(shù)與數(shù)學(xué)本身是一家，拋開(kāi)計(jì)算機(jī)專業(yè)知識(shí)不提，上述問(wèn)題其實(shí)可以回歸成一個(gè)數(shù)學(xué)問(wèn)題。數(shù)學(xué)問(wèn)題的目標(biāo)是在一個(gè)數(shù)字序列中尋找重復(fù)的那個(gè)數(shù)。根據(jù)題目意思可以看出，1～1000個(gè)數(shù)中除了唯一一個(gè)數(shù)重復(fù)以外，其他各數(shù)有且僅有出現(xiàn)一次，由數(shù)學(xué)性質(zhì)可知，這1001個(gè)數(shù)包括1到1000中的每一個(gè)數(shù)各1次，外加1到1000中某一個(gè)數(shù)，很顯然，1001個(gè)數(shù)中有1000個(gè)數(shù)是固定的，唯一一個(gè)不固定的數(shù)也知道其范圍(1～1000中某一個(gè)數(shù))，那么最容易想到的方法就是累加求和法。

所謂累加求和法，指的是將數(shù)組中的所有N+1(此處N的值取1000)個(gè)元素相加，然后用得到的和減去1+2+3+……N(此處N的值為1000)的和，得到的差即為重復(fù)的元素的值。這一點(diǎn)不難證明。

由于1001個(gè)數(shù)的數(shù)據(jù)量較大，不方便說(shuō)明以上算法。為了簡(jiǎn)化問(wèn)題，以數(shù)組序列(1，3，4，2，5，3)為例。該數(shù)組長(zhǎng)度為6，除了數(shù)字3以外，其他4個(gè)數(shù)字沒(méi)有重復(fù)。按照上述方法，首先，計(jì)算數(shù)組中所有元素的和sumb，sumb=1+3+4+2+5+3=18，數(shù)組中只包含1～5的數(shù)，計(jì)算1到5一共5個(gè)數(shù)字的和suma，suma=1+2+3+4+5=15；所以，重復(fù)的數(shù)字的值為sumb-suma=3。由于本方法的代碼實(shí)現(xiàn)較為簡(jiǎn)單，此處就不提供代碼了，有興趣的讀者可以自己實(shí)現(xiàn)。

算法性能分析：

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

在使用求和法計(jì)算時(shí)，需要注意一個(gè)問(wèn)題，即當(dāng)數(shù)據(jù)量巨大時(shí)，有可能會(huì)導(dǎo)致計(jì)算結(jié)果溢出。以本題為例，1～1000范圍內(nèi)的1000個(gè)數(shù)累加，其和為(1+1000)*1000/2，即500500，普通的int型變量能夠表示出來(lái)，所以，本題中不存在此問(wèn)題。但如果累加的數(shù)值巨大時(shí)，就很有可能溢出了。

此處是否還可以繼續(xù)發(fā)散一下，如果累加求和法能夠成立的話，累乘求積法是不是也是可以成立的呢?只是累加求積法在使用的過(guò)程中很有可能會(huì)存在數(shù)據(jù)越界的情況，如果再由此定義一個(gè)大數(shù)乘法，那就有點(diǎn)得不償失了。所以，求積的方式理論上是成立的，只是在實(shí)際的使用過(guò)程中可操作性不強(qiáng)而已，一般更加推薦累加求和法。

方法三：異或法

采用以上累加求和的方法，雖然能夠解決本題的問(wèn)題，但也存在一個(gè)潛在的風(fēng)險(xiǎn)，就是當(dāng)數(shù)組中的元素值太大或者數(shù)組太長(zhǎng)時(shí)，計(jì)算的和值有可能會(huì)出現(xiàn)溢出的情況，進(jìn)而無(wú)法求解出數(shù)組中的唯一重復(fù)元素。

鑒于求和法存在的局限性，可以采用位運(yùn)算中異或的方法。根據(jù)異或運(yùn)算的性質(zhì)可知，當(dāng)相同元素異或時(shí)，其運(yùn)算結(jié)果為0，當(dāng)相異元素異或時(shí)，其運(yùn)算結(jié)果為非0，任何數(shù)與數(shù)字0進(jìn)行異或運(yùn)算，其運(yùn)算結(jié)果為該數(shù)。本題中，正好可以使用到此方法，即將數(shù)組里的元素逐一進(jìn)行異或運(yùn)算，得到的值再與數(shù)字1、2、3……N進(jìn)行異或運(yùn)算，得到的最終結(jié)果即為所求的重復(fù)元素。

以數(shù)組(1，3，4，2，5，3)為例。(1^3^4^2^5^3)^(1^2^3^4^5)=(1^1)^(2^2)^(3^3^3)^(4^4)^(5^5)=0^0^3^0^0=3。

示例代碼如下：

deffindDup(array):

ifNone==array:

return-1

lens=len(array)

result=0

i=0

whilei＜lens:

result^=array[i]

i+=1

j=1

whilej＜lens:

result^=j

j+=1

returnresult

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

3

算法性能分析：

上述方法的時(shí)間復(fù)雜度為O(N)，也沒(méi)有申請(qǐng)輔助的存儲(chǔ)空間。

方法四：數(shù)據(jù)映射法

數(shù)組取值操作可以看作一個(gè)特殊的函數(shù)f:D→R，定義域?yàn)橄聵?biāo)值0～1000，值域?yàn)?到1000。如果對(duì)任意一個(gè)數(shù)i，把f(i)叫做它的后繼，i叫f(i)的前驅(qū)。0只有后繼，沒(méi)有前驅(qū)，其他數(shù)字既有后繼也有前驅(qū)，重復(fù)的那個(gè)數(shù)字有兩個(gè)前驅(qū)，將利用這些特征。

采用此種方法，可以發(fā)現(xiàn)一個(gè)規(guī)律，即從0開(kāi)始畫(huà)一個(gè)箭頭指向它的后繼，從它的后繼繼續(xù)指向后繼的后繼，這樣，必然會(huì)有一個(gè)結(jié)點(diǎn)指向之前已經(jīng)出現(xiàn)過(guò)的數(shù)，即為重復(fù)的數(shù)。

利用下標(biāo)與單元中所存儲(chǔ)的內(nèi)容之間的特殊關(guān)系，進(jìn)行遍歷訪問(wèn)單元，一旦訪問(wèn)過(guò)的單元賦予一個(gè)標(biāo)記(把數(shù)組中元素變?yōu)樗南喾磾?shù))，利用標(biāo)記作為發(fā)現(xiàn)重復(fù)數(shù)字的關(guān)鍵。

以數(shù)組array=(1,3,4,3,5,2)為例。從下標(biāo)0開(kāi)始遍歷數(shù)組，

(1)array[0]的值為1，說(shuō)明沒(méi)有被遍歷過(guò)，接下來(lái)遍歷下標(biāo)為1的元素，同時(shí)標(biāo)記已遍歷過(guò)的元素(變?yōu)橄喾磾?shù))：array=(1,3,4,3,5,2)；

(2)array[1]的值為3，說(shuō)明沒(méi)被遍歷過(guò)，接下來(lái)遍歷下標(biāo)為3的元素，同時(shí)標(biāo)記已遍歷過(guò)的元素：array=(-1,-3,4,3,5,2)；

(3)array[3]的值為3，說(shuō)明沒(méi)被遍歷過(guò)，接下來(lái)遍歷下標(biāo)為3的元素，同時(shí)標(biāo)記已遍歷過(guò)的元素：

array=(-1,-3,4,-3,5,2);

(4)array[3]的值為-3，說(shuō)明3已經(jīng)被遍歷過(guò)了，找到了重復(fù)的元素。

示例代碼如下：

deffindDup(array):

ifNone=array:

return-1

lens=len(array)

index=0

i=0

whileTrue:

#數(shù)組中的元素的值只能小于len,否則會(huì)越界

ifarray[i]＞=lens:

return-1

ifarray[index]＜0:

break

#訪問(wèn)過(guò),通過(guò)變相反數(shù)的方法進(jìn)行標(biāo)記

array[index]*=-1

#index的后繼為array[index]

index=-1*array[index]

ifindex＞=lens:

print"數(shù)組中有非法數(shù)字"

return-1

returnindex

算法說(shuō)明：

因?yàn)槊總€(gè)數(shù)在數(shù)組中都有自己應(yīng)該在的位置，如果一個(gè)數(shù)是在自己應(yīng)該在的位置(在本題中就是它的值就是它的下標(biāo)，即所在的位置)，那永遠(yuǎn)不會(huì)對(duì)它進(jìn)行調(diào)換，也就是不會(huì)訪問(wèn)到它，除非它就是那個(gè)多出的數(shù)，那與它相同的數(shù)訪問(wèn)到它的時(shí)候就是結(jié)果了；如果一個(gè)數(shù)的位置是鳩占鵲巢，所在的位置不是它應(yīng)該待的地方，那它會(huì)去找它應(yīng)該在的位置，在它位置的數(shù)也應(yīng)該去找它應(yīng)該在的位置，碰到了負(fù)數(shù)，也就是說(shuō)已經(jīng)出現(xiàn)了這個(gè)數(shù)，所以就得出了結(jié)果。

算法性能分析：

上述方法的時(shí)間復(fù)雜度為O(N)，也沒(méi)有申請(qǐng)輔助的存儲(chǔ)空間。

這種方法的缺點(diǎn)是修改了數(shù)組中元素的值，當(dāng)然也可以在找到重復(fù)元素之后對(duì)數(shù)組進(jìn)行一次遍歷，把數(shù)組中的元素改為它的絕對(duì)值的方法來(lái)恢復(fù)對(duì)數(shù)組的修改。

方法五：環(huán)形相遇法

該方法就是采用類似于單鏈表是否存在環(huán)的方法進(jìn)行問(wèn)題求解。“判斷單鏈表是否存在環(huán)”是一個(gè)非常經(jīng)典的問(wèn)題，同時(shí)單鏈表可以采用數(shù)組實(shí)現(xiàn)，此時(shí)每個(gè)元素值作為next指針指向下一個(gè)元素。本題可以轉(zhuǎn)化為“已知一個(gè)單鏈表中存在環(huán)，找出環(huán)的入口點(diǎn)”這種想法。具體思路如下：將array[i]看作第i個(gè)元素的索引，即：array[i]-＞array[array[i]]-＞array[array[array[i]]]-＞array[array[array[array[i]]]]-＞…最終形成一個(gè)單鏈表，由于數(shù)組a中存在重復(fù)元素，則一定存在一個(gè)環(huán)，且環(huán)的入口元素即為重復(fù)元素。

該題的關(guān)鍵在于，數(shù)組array的大小是n，而元素的范圍是[1，n-1]，所以，array[0]不會(huì)指向自己，進(jìn)而不會(huì)陷入錯(cuò)誤的自循環(huán)。如果元素的范圍中包含0，則該題不可直接采用該方法。

以數(shù)組序列[1,3,4,2,5,3]為例。按照上述規(guī)則，這個(gè)數(shù)組序列對(duì)應(yīng)的單鏈表如下圖所示：

從上圖可以看出這個(gè)鏈表有環(huán)，且環(huán)的入口點(diǎn)為3，所以，這個(gè)數(shù)組中重復(fù)元素為3。

在實(shí)現(xiàn)的時(shí)候可以參考求單鏈表環(huán)的入口點(diǎn)的算法：用兩個(gè)速度不同的變量slow和fast來(lái)訪問(wèn)，其中，slow每次前進(jìn)一步，fast每次前進(jìn)兩步。在有環(huán)結(jié)構(gòu)中，它們總會(huì)相遇。接著從數(shù)組首元素與相遇點(diǎn)開(kāi)始分別遍歷，每次各走一步，它們必定相遇，且相遇第一點(diǎn)為環(huán)的入口點(diǎn)。

示例代碼如下：

deffindDup(array):

ifNone==array:

return-1

slow=0

fast=0

whileTrue:

fast=array[array[fast]]#fast一次走兩步

slow=array[slow]#slow一次走一步

ifslow==fast:#找到相遇點(diǎn)

break

fast=0

whileTrue:

fast=array[fast]

slow=array[slow]

ifslow==fast:#找到入口點(diǎn)

returnslow

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

3

算法性能分析：

上述方法的時(shí)間復(fù)雜度為O(N)，也沒(méi)有申請(qǐng)輔助的存儲(chǔ)空間。

當(dāng)數(shù)組中的元素不合理的時(shí)候，上述算法有可能會(huì)有數(shù)組越界的可能性，因此，為了安全性和健壯性，可以在執(zhí)行fast=array[array[fast]];slow=array[slow];操作的時(shí)候分別檢查array[slow]與array[fast]的值是否會(huì)越界，如果越界，則說(shuō)明提供的數(shù)據(jù)不合法。)解析：[考點(diǎn)]如何找出數(shù)組中唯一的重復(fù)元素。2.

給定數(shù)組a1,a2,a3,…an，要求找出數(shù)組中的最大值和最小值。假設(shè)數(shù)組中的值兩兩各不相同。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(雖然題目沒(méi)有時(shí)間復(fù)雜度與空間復(fù)雜度的要求，但是給出的算法的時(shí)間復(fù)雜度肯定是越低越好。

方法一：蠻力法

查找數(shù)組中元素的最大值與最小值并非是一件困難的事情，最容易想到的方法就是蠻力法。具體過(guò)程如下：首先定義兩個(gè)變量max與min，分別記錄數(shù)組中最大值與最小值，并將其都初始化為數(shù)組的首元素的值，然后從數(shù)組的第二個(gè)元素開(kāi)始遍歷數(shù)組元素，如果遇到的數(shù)組元素的值比max大，則該數(shù)組元素的值為當(dāng)前的最大值，并將該值賦給max，如果遇到的數(shù)組元素的值比min小，則該數(shù)組元素的值為當(dāng)前的最小值，并將該值賦給min。

算法性能分析：

上述方法的時(shí)間復(fù)雜度為O(n)，但很顯然，以上這種方法稱不上是最優(yōu)算法，因?yàn)樽畈钋闆r下比較的次數(shù)達(dá)到了2n-2次(數(shù)組第一個(gè)元素首先賦值給max與min，接下來(lái)的n-1個(gè)元素都需要分別跟max與min比較一次，一次比較次數(shù)為2n-2)，最好的情況下比較次數(shù)為n-1。是否可以將比較次數(shù)降低呢?回答是肯定的，分治法就是一種更高效的方法。

方法二：分治法

分治法就是將一個(gè)規(guī)模為n的、難以直接解決的大問(wèn)題，分割為k個(gè)規(guī)模較小的子問(wèn)題，采取各個(gè)擊破、分而治之的策略得到各個(gè)子問(wèn)題的解，然后將各個(gè)子問(wèn)題的解進(jìn)行合并，從而得到原問(wèn)題的解的一種方法。

本題中，當(dāng)采用分治法求解時(shí)，就是將數(shù)組兩兩一對(duì)分組，如果數(shù)組元素個(gè)數(shù)為奇數(shù)個(gè)，就把最后一個(gè)元素單獨(dú)分為一組，然后分別對(duì)每一組中相鄰的兩個(gè)元數(shù)進(jìn)行比較，把二者中值小的數(shù)放在數(shù)組的左邊，值大的數(shù)放在數(shù)組右邊，只需要比較n/2次就可以將數(shù)組分組完成。然后可以得出結(jié)論：最小值一定在每一組的左邊部分，最大值一定在每一組的右邊部分，接著只需要在每一組的左邊部分找最小值，右邊部分找最大值，查找分別需要比較n/2-1次和n/2-1次；因此，總共比較的次數(shù)大約為n/2*3=3n/2-2次。

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

classMaxMin:

def__new__(self):

self.max=None

self.min=None

defgetMax(self):returnself.max

defgetMin(self):returnself.min

defGetmaxAndmin(self,arr):

ifarr==None:

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

return

i=0

lens=len(arr)

self.max=arr[0]

self.min=arr[0]

#兩兩分組,把較小的數(shù)放到左半部分,較大的數(shù)放到右半部分

i=0

whilei＜(lens-1):

ifarr[i]＞arr[i+1]:

tmp=arr[i]

arr[i]=arr[i+1]

arr[i+1]=tmp

i+=2

#在各個(gè)分組的左半部分找最小值

self.min=arr[0]

i=2

whilei＜lens:

ifarr[i]＜self.min:

self.min=arr[i]

i+=2

#在各個(gè)分組的右半部分找最大值

self.max=arr[1]

i=3

whilei＜lens:

ifarr[i]＞self.max:

self.max=arr[i]

i+=2

#如果數(shù)組中元素個(gè)數(shù)是奇數(shù)個(gè),最后一個(gè)元素被分為一組,需要特殊處理

iflens%2=1:

ifself.max＜arr[lens-1]:

self.max=arr[lens-1]

ifself.min＞arr[lens-1]:

self.min=arr[lens-1]

if__name__=="__main__":

array=[7,3,19,40,4,7,1]

m=MaxMin()

m.GetmaxAndmin(array)

print"max="+str(m.getMax())

print"min="+str(m.getMin))

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

max=40

min=1

方法三：變形的分治法

除了以上所示的分治法以外，還有一種分治法的變形，其具體步驟如下：將數(shù)組分成左右兩部分，先求出左半部分的最大值和最小值，再求出右半部分的最大值和最小值，然后綜合起來(lái)，左右兩部分的最大值中的較大值即為合并后的數(shù)組的最大值，左右兩部分的最小值中的較小值即為合并后的數(shù)組的最小值，通過(guò)此種方法即可求合并后的數(shù)組的最大值與最小值。

以上過(guò)程是個(gè)遞歸過(guò)程，對(duì)于劃分后的左右兩部分，同樣重復(fù)這個(gè)過(guò)程，直到劃分區(qū)間內(nèi)只剩一個(gè)元素或者兩個(gè)元素為止。

示例代碼如下：

classMaxMin:

#返回值列表中有兩個(gè)元素,第一個(gè)元素為子數(shù)組的最小值,第二個(gè)元素為最大值

defgetMaxMin(self,array,l,r):

ifarray==None:

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

return

list=[]

m=(1+r)/2#求中點(diǎn)

ifl==r:#l與r之間只有一個(gè)元素

list.append(array[l])

list.append(array[l])

returnlist

if1+1=r:#1與r之間只有兩個(gè)元素

ifarray[l]＞=array[r]:

max=array[l]

min=array[r]

else:

max=array[r]

min=array[l]

list.append(min)

list.append(max)

returnlist

#遞歸計(jì)算左半部份

lList=self.getMaxMin(array,l,m)

#遞歸計(jì)算右半部份

rList=self.getMaxMin(array,m+1,r)

#總的最大值

max=lList[1]if(lList[1]＞rList[l])elserList[1]

#總的最小值

min=lList[0]if(lList[0]＜rList[0])elserList[0]

list,append(min)

list.append(max)

returnlist

if__name__=="__main__":

array=[7,3,19,40,4,7,1]

m=MaxMin()

result=m.getMaxMin(array,0,len(array)-1)

print"max="+str(result[1])

print"min="+str(result[0])

算法性能分析：

這種方法與方法二的思路從本質(zhì)上講是相同的，只不過(guò)這種方法是使用遞歸的方式實(shí)現(xiàn)的，因此，比較次數(shù)為3n/2-2。)解析：[考點(diǎn)]如何查找數(shù)組中元素的最大值和最小值。3.

把一個(gè)有序數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組[3,4,5,1,2]為數(shù)組[1,2,3,4,5]的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(Python中可以使用列表來(lái)表示有序數(shù)組，因此示例中都用列表來(lái)表示有序數(shù)組。

其實(shí)這是一個(gè)非?；竞统Ｓ玫臄?shù)組操作，它的描述如下：

有一個(gè)數(shù)組X[0...n-1]，現(xiàn)在把它分為兩個(gè)子數(shù)組：x1[0...m]和x2[m+1...n-1]，交換這兩個(gè)子數(shù)組，使數(shù)組x由x1x2變成x2x1，例如x=[1,2,3,4,5,6,7,8,9]，x1=[1,2,3,4,5],x2=[6,7,8,9]，交換后，x=[6,7,8,9,1,2,3,4,5]。

對(duì)于本題的解決方案，最容易想到的，也是最簡(jiǎn)單的方法就是直接遍歷法。但是這種方法顯然沒(méi)有用到題目中旋轉(zhuǎn)數(shù)組的特性，因此，它的效率比較低下，下面介紹一種比較高效的二分查找法。

通過(guò)數(shù)組的特性可以發(fā)現(xiàn)，數(shù)組元素首先是遞增的，然后突然下降到最小值，然后再遞增。雖然如此，但是還有下面三種特殊情況需要注意：

(1)數(shù)組本身是沒(méi)有發(fā)生過(guò)旋轉(zhuǎn)的，是一個(gè)有序的數(shù)組，例如序列[1,2,3,4,5,6]。

(2)數(shù)組中元素值全部相等，例如序列[1,1,1,1,1,1]。

(3)數(shù)組中元素值大部分都相等，例如序列[1,0,1,1,1,1]。

通過(guò)旋轉(zhuǎn)數(shù)組的定義可知，經(jīng)過(guò)旋轉(zhuǎn)之后的數(shù)組實(shí)際上可以劃分為兩個(gè)有序的子數(shù)組，前面的子數(shù)組的元素值都大于或者等于后面子數(shù)組的元素值。可以根據(jù)數(shù)組元素的這個(gè)特點(diǎn)，采用二分查找的思想不斷縮小查找范圍，最終找出問(wèn)題的解決方案，具體實(shí)現(xiàn)思路如下所示：

按照二分查找的思想，給定數(shù)組arr，首先定義兩個(gè)變量low和high，分別表示數(shù)組的第一個(gè)元素和最后一個(gè)元素的下標(biāo)。按照題目中對(duì)旋轉(zhuǎn)規(guī)則的定義，第一個(gè)元素應(yīng)該是大于或者等于最后一個(gè)元素的(當(dāng)旋轉(zhuǎn)個(gè)數(shù)為0，即沒(méi)有旋轉(zhuǎn)的時(shí)候，要單獨(dú)處理，直接返回?cái)?shù)組第一個(gè)元素)。接著遍歷數(shù)組中間的元素arr[mid]，其中mid=(high+low)/2。

(1)如果arr[mid]＜arr[mid-1]，則arr[mid]一定是最小值；

(2)如果arr[mid+1]＜arr[mid]，則arr[mid+1]一定是最小值；

(3)如果arr[high]＞arr[mid]，則最小值一定在數(shù)組左半部分；

(4)如果arr[mid]＞arr[low]，則最小值一定在數(shù)組右半部分；

(5)如果arr[low]==arr[mid]且arr[high]==arr[mid]，則此時(shí)無(wú)法區(qū)分最小值是在數(shù)組的左半部分還是右半部分(例如：[2,2,2,2,1,2]，[2,1,2,2,2,2,2])。在這種情況下，只能分別在數(shù)組的左右兩部分找最小值minL與minR，最后求出minL與minR的最小值。

示例代碼如下：

#python中可以使用列表來(lái)表示有序數(shù)組,因此示例代碼中使用列表來(lái)表示有序數(shù)組。

defgetMin_1(arr,low,high):

#如果旋轉(zhuǎn)個(gè)數(shù)為0,即沒(méi)有旋轉(zhuǎn),單獨(dú)處理,直接返回?cái)?shù)組頭元素

ifhigh＜low:

returnarr[0]

#只剩下一個(gè)元素一定是最小值

ifhigh==low:

returnarr[low]

#mid=(low+high)/2,采用下面寫(xiě)法防止溢出

mid=low+((high-low)＞＞1)

#判斷是否arr[mid]為最小值

ifarr[mid]＜arr[mid-1]:

returnarr[mid]

#判斷是否arr[mid+1]為最小值

elifarr[mid+1]＜arr[mid]:

returnarr[mid+1]

#最小值一定在數(shù)組左半部分

elifarr[high]＞arr[mid]:

returngetMin(arr,low,mid-1)

#最小值一定在數(shù)組右半部分

elifarr[mid]＞arr[low]:

returngetMin(arr,mid+1,high)

#arr[low]==arr[mid]&&arr[high]=arr[mid]

#這種情況下無(wú)法確定最小值所在的位置,需要在左右兩部分分別進(jìn)行查找

else:

returnmin(getMin(arr,low,mid-1),getMin(arr,mid+1,high)

defgetMin(arr):

ifNone==arr:

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

return

else:

returngetMin_1(arr,0,len(arr)-1)

if__name__=="__main__":

array1=[5,6,1,2,3,4]

mins=getMin(arrayl)

printmins

array2=[1,1,0,1]

mins=getMin(array2)

printmins

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

1

0

算法性能分析：

一般而言，二分查找的時(shí)間復(fù)雜度為O(log2N)，對(duì)于這道題而言，大部分情況下時(shí)間復(fù)雜度為O(log2N)，只有每次都滿足第(5)條的時(shí)候才需要對(duì)數(shù)組中所有元素都進(jìn)行遍歷，因此，這種方法在最壞的情況下的時(shí)間復(fù)雜度為O(N)。)解析：[考點(diǎn)]如何找出旋轉(zhuǎn)數(shù)組的最小元素。4.

給定一個(gè)由n-1個(gè)整數(shù)組成的未排序的數(shù)組序列，其元素都是1到n中的不同的整數(shù)。請(qǐng)寫(xiě)出一個(gè)尋找數(shù)組序列中缺失整數(shù)的線性時(shí)間算法。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(方法一：累加求和

首先分析一下數(shù)學(xué)性質(zhì)。假設(shè)缺失的數(shù)字是X，那么這n-1個(gè)數(shù)一定是1～n之間除了X以外的所有數(shù)，試想一下，1～n一共n個(gè)數(shù)的和是可以求出來(lái)的，數(shù)組中的元素的和也是可以求出來(lái)的，二者相減，其值是不是就是缺失的數(shù)字X的值呢?

為了更好地說(shuō)明上述方法，舉一個(gè)簡(jiǎn)單的例子。假設(shè)數(shù)組序列為[2,1,4,5]一共4個(gè)元素，n的值為5，要想找出這個(gè)缺失的數(shù)字，可以首先對(duì)1到5五個(gè)數(shù)字求和，求和結(jié)果為15(1+2+3+4+5=15)，而數(shù)組元素的和為array[0]+array[1]+array[2]+array[3]=2+1+4+5=12，所以，缺失的數(shù)字為15-12=3。

通過(guò)上面的例子可以很容易形成以下具體思路：定義兩個(gè)數(shù)suma與sumb，其中，suma表示的是這n-1個(gè)數(shù)的和，sumb表示的是這n個(gè)數(shù)的和，很顯然，缺失的數(shù)字的值即為sumb-suma的值。

示例代碼如下：

defgetNum(arr):

ifarr==Noneorlen(arr)＜=0:

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

return-1

suma=0

sumb=0

i=0

whilei＜len(arr):

suma=suma+arr[i]

sumb=sumb+i

i+=1

sumb=sumb+len(arr)+len(arr)+1

returnsumb-suma

if__name__=="__main__":

arr=[1,4,3,2,7,5]

printgetNum(arr)

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

6

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(N)。需要注意的是，在求和的過(guò)程中，計(jì)算結(jié)果有溢出的可能性。所以，為了避免這種情況的發(fā)生，在進(jìn)行數(shù)學(xué)運(yùn)算時(shí)，可以考慮位運(yùn)算，畢竟位運(yùn)算性能最好，下面介紹如何用位運(yùn)算來(lái)解決這個(gè)問(wèn)題。

方法二：異或法

在解決這個(gè)問(wèn)題前，首先回顧一下異或運(yùn)算的性質(zhì)。簡(jiǎn)單點(diǎn)說(shuō)，在進(jìn)行異或運(yùn)算時(shí)，當(dāng)參與運(yùn)算的兩個(gè)數(shù)相同時(shí)，異或結(jié)果為假，當(dāng)參與異或運(yùn)算的兩個(gè)數(shù)不相同時(shí)，異或結(jié)果為真。

1到n這n個(gè)數(shù)異或的結(jié)果為a=1^2^3^…^n。假設(shè)數(shù)組中缺失的數(shù)為m，那么數(shù)組中這n-1個(gè)數(shù)異或的結(jié)果為b=1^2^3^…(m-1)^(m+1)^…^n。由此可知，a^b=(1^1)^(2^2)^…(m-1)^(m-1)^m^(m+1)^(m+1)^…^(n^n)=m。根據(jù)這個(gè)公式可以得知本題的主要思路為：定義兩個(gè)數(shù)a與b，其中，a表示的是1到n這n個(gè)數(shù)的異或運(yùn)算結(jié)果，b表示的是數(shù)組中的n-1個(gè)數(shù)的異或運(yùn)算結(jié)果，缺失的數(shù)字的值即為a^b的值。

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

defgetNum(arr):

ifarr==Noneorlen(arr)＜=0:

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

return-1

a=arr[0]

b=1

lens=len(arr)

i=1

whilei＜lens:

a=a^arr[i]

i+=1

i=2

whilei＜=lens+1:

b=b^i

i+=1

returna^b

if__name__="__main__":

arr=[1,4,3,2,7,5]

printgetNum(arr)

算法性能分析：

這種方法在計(jì)算結(jié)果a的時(shí)候?qū)?shù)組進(jìn)行了一次遍歷，時(shí)間復(fù)雜度為O(N)，接著在計(jì)算b的時(shí)候循環(huán)執(zhí)行的次數(shù)為N，時(shí)間復(fù)雜度也為O(N)。因此，這種方法的時(shí)間復(fù)雜度為O(N)。)解析：[考點(diǎn)]如何找出數(shù)組中丟失的數(shù)。5.

數(shù)組中有N+2個(gè)數(shù)，其中，N個(gè)數(shù)出現(xiàn)了偶數(shù)次，2個(gè)數(shù)出現(xiàn)了奇數(shù)次(這兩個(gè)數(shù)不相等)，請(qǐng)用O(1)的空間復(fù)雜度，找出這兩個(gè)數(shù)。注意：不需要知道具體位置，只需要找出這兩個(gè)數(shù)。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(方法一：字典法

對(duì)于本題而言，定義一個(gè)字典，把數(shù)組元素的值作為key，遍歷整個(gè)數(shù)組，如果key值不存在，則將value設(shè)為1，如果key值已經(jīng)存在，則翻轉(zhuǎn)該值(如果為0，則翻轉(zhuǎn)為1；如果為1，則翻轉(zhuǎn)為0)，在完成數(shù)組遍歷后，字典中value為1的就是出現(xiàn)奇數(shù)次的數(shù)。

例如：給定數(shù)組=[3,5,6,6,5,7,2,2]；

首先遍歷3，字典中的元素為：{3:1}；

遍歷5，字典中的元素為：{3:1,5:1}；

遍歷6，字典中的元素為：{3:1,5:1,6:1}；

遍歷6，字典中的元素為：{3:1,5:1,6:0}；

遍歷5，字典中的元素為：{3:1,5:0,6:0}；

遍歷7，字典中的元素為：{3:1,5:0,6:0,7:1}；

遍歷2，字典中的元素為：{3:1,5:0,6:0,7:1,2:1}；

遍歷2，字典中的元素為：{3:1,5:0,6:0,7:1,2:0}；

顯然，出現(xiàn)1次的數(shù)組元素為3和7。

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

defget2Num(arr):

ifarr==Noneorlen(arr)＜1:

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

return

dic=dict()

i=0

whilei＜len(arr):

#dic中沒(méi)有這個(gè)數(shù)字,說(shuō)明第一次出現(xiàn),value賦值為1

ifarr[i]notindic:

dic[arr[i]]=1

#當(dāng)前遍歷的值在dic中存在,說(shuō)明前面出現(xiàn)過(guò),value賦值為0

e