Python程序員面試分類真題7

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

數(shù)字1～1000放在含有1001個元素的數(shù)組中，其中只有唯一的一個元素值重復(fù)，其他數(shù)字均只出現(xiàn)一次。設(shè)計一個算法，將重復(fù)元素找出來，要求每個數(shù)組元素只能訪問一次。如果不（江南博哥）使用輔助存儲空間，能否設(shè)計一個算法實現(xiàn)?正確答案：方法一：空間換時間法

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

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

示例代碼如下：

"""

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

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

返回值:重復(fù)元素的值,如果無重復(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)

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

3

算法性能分析：

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

方法二：累加求和法

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

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

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

算法性能分析：

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

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

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

方法三：異或法

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

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

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

3

算法性能分析：

上述方法的時間復(fù)雜度為O(N)，也沒有申請輔助的存儲空間。

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

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

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

利用下標(biāo)與單元中所存儲的內(nèi)容之間的特殊關(guān)系，進(jìn)行遍歷訪問單元，一旦訪問過的單元賦予一個標(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開始遍歷數(shù)組，

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

(2)array[1]的值為3，說明沒被遍歷過，接下來遍歷下標(biāo)為3的元素，同時標(biāo)記已遍歷過的元素：array=(-1,-3,4,3,5,2)；

(3)array[3]的值為3，說明沒被遍歷過，接下來遍歷下標(biāo)為3的元素，同時標(biāo)記已遍歷過的元素：

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

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

示例代碼如下：

deffindDup(array):

ifNone=array:

return-1

lens=len(array)

index=0

i=0

whileTrue:

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

ifarray[i]＞=lens:

return-1

ifarray[index]＜0:

break

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

array[index]*=-1

#index的后繼為array[index]

index=-1*array[index]

ifindex＞=lens:

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

return-1

returnindex

算法說明：

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

算法性能分析：

上述方法的時間復(fù)雜度為O(N)，也沒有申請輔助的存儲空間。

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

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

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

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

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

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

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

示例代碼如下：

deffindDup(array):

ifNone==array:

return-1

slow=0

fast=0

whileTrue:

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

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

ifslow==fast:#找到相遇點

break

fast=0

whileTrue:

fast=array[fast]

slow=array[slow]

ifslow==fast:#找到入口點

returnslow

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

3

算法性能分析：

上述方法的時間復(fù)雜度為O(N)，也沒有申請輔助的存儲空間。

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

2.

給定數(shù)組a1,a2,a3,…an，要求找出數(shù)組中的最大值和最小值。假設(shè)數(shù)組中的值兩兩各不相同。正確答案：雖然題目沒有時間復(fù)雜度與空間復(fù)雜度的要求，但是給出的算法的時間復(fù)雜度肯定是越低越好。

方法一：蠻力法

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

算法性能分析：

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

方法二：分治法

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

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

實現(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

#在各個分組的左半部分找最小值

self.min=arr[0]

i=2

whilei＜lens:

ifarr[i]＜self.min:

self.min=arr[i]

i+=2

#在各個分組的右半部分找最大值

self.max=arr[1]

i=3

whilei＜lens:

ifarr[i]＞self.max:

self.max=arr[i]

i+=2

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

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))

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

max=40

min=1

方法三：變形的分治法

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

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

示例代碼如下：

classMaxMin:

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

defgetMaxMin(self,array,l,r):

ifarray==None:

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

return

list=[]

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

ifl==r:#l與r之間只有一個元素

list.append(array[l])

list.append(array[l])

returnlist

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

ifarray[l]＞=array[r]:

max=array[l]

min=array[r]

else:

max=array[r]

min=array[l]

list.append(min)

list.append(max)

returnlist

#遞歸計算左半部份

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

#遞歸計算右半部份

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ì)上講是相同的，只不過這種方法是使用遞歸的方式實現(xiàn)的，因此，比較次數(shù)為3n/2-2。[考點]如何查找數(shù)組中元素的最大值和最小值

3.

把一個有序數(shù)組最開始的若干個元素搬到數(shù)組的末尾，稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組[3,4,5,1,2]為數(shù)組[1,2,3,4,5]的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。正確答案：Python中可以使用列表來表示有序數(shù)組，因此示例中都用列表來表示有序數(shù)組。

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

有一個數(shù)組X[0...n-1]，現(xiàn)在把它分為兩個子數(shù)組：x1[0...m]和x2[m+1...n-1]，交換這兩個子數(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]。

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

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

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

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

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

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

按照二分查找的思想，給定數(shù)組arr，首先定義兩個變量low和high，分別表示數(shù)組的第一個元素和最后一個元素的下標(biāo)。按照題目中對旋轉(zhuǎn)規(guī)則的定義，第一個元素應(yīng)該是大于或者等于最后一個元素的(當(dāng)旋轉(zhuǎn)個數(shù)為0，即沒有旋轉(zhuǎn)的時候，要單獨處理，直接返回數(shù)組第一個元素)。接著遍歷數(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]，則此時無法區(qū)分最小值是在數(shù)組的左半部分還是右半部分(例如：[2,2,2,2,1,2]，[2,1,2,2,2,2,2])。在這種情況下，只能分別在數(shù)組的左右兩部分找最小值minL與minR，最后求出minL與minR的最小值。

示例代碼如下：

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

defgetMin_1(arr,low,high):

#如果旋轉(zhuǎn)個數(shù)為0,即沒有旋轉(zhuǎn),單獨處理,直接返回數(shù)組頭元素

ifhigh＜low:

returnarr[0]

#只剩下一個元素一定是最小值

ifhigh==low:

returnarr[low]

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

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]

#這種情況下無法確定最小值所在的位置,需要在左右兩部分分別進(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

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

1

0

算法性能分析：

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

4.

給定一個由n-1個整數(shù)組成的未排序的數(shù)組序列，其元素都是1到n中的不同的整數(shù)。請寫出一個尋找數(shù)組序列中缺失整數(shù)的線性時間算法。正確答案：方法一：累加求和

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

為了更好地說明上述方法，舉一個簡單的例子。假設(shè)數(shù)組序列為[2,1,4,5]一共4個元素，n的值為5，要想找出這個缺失的數(shù)字，可以首先對1到5五個數(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。

通過上面的例子可以很容易形成以下具體思路：定義兩個數(shù)suma與sumb，其中，suma表示的是這n-1個數(shù)的和，sumb表示的是這n個數(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)

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

6

算法性能分析：

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

方法二：異或法

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

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

實現(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)

算法性能分析：

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

5.

數(shù)組中有N+2個數(shù)，其中，N個數(shù)出現(xiàn)了偶數(shù)次，2個數(shù)出現(xiàn)了奇數(shù)次(這兩個數(shù)不相等)，請用O(1)的空間復(fù)雜度，找出這兩個數(shù)。注意：不需要知道具體位置，只需要找出這兩個數(shù)。正確答案：方法一：字典法

對于本題而言，定義一個字典，把數(shù)組元素的值作為key，遍歷整個數(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。

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

defget2Num(arr):

ifarr==Noneorlen(arr)＜1:

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

return

dic=dict()

i=0

whilei＜len(arr):

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

ifarr[i]notindic:

dic[arr[i]]=1

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

else:

dic[arr[i]]=0

i+=1

fork,vind