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

一個數組里，除了三個數是唯一出現的，其余的數都出現偶數次，找出這三個數中的任意一個。比如數組序列為[1,2,4,5,6,4,2]，只有1，5，6這三個數字是唯一出現的，（江南博哥）數字2與4均出現了偶數次(2次)，只需要輸出數字1，5，6中的任意一個就行。正確答案：根據題目描述可以得到如下幾個有用的信息：

(1)數組中元素個數一定是奇數個；

(2)由于只有三個數字出現過一次，顯然這三個數字不相同，因此，這三個數對應的二進制數也不可能完全相同。

由此可知，必定能找到二進制數中的某一個bit來區分這三個數(這一個bit的取值或者為0，或者為1)，當通過這一個bit的值對數組進行分組的時候，這三個數一定可以被分到兩個子數組中，并且其中一個子數組中分配了兩個數字，而另一個子數組分配了一個數字，而其他出現兩次的數字肯定是成對出現在子數組中的。此時我們只需要重點關注哪個子數組中分配了這三個數中的其中一個，就可以很容易地找出這個數字了。當數組被分成兩個子數組時，這一個bit的值為1的數被分到一個子數組subArray1，這一個bit的值為0的數被分到另外一個子數組subArray0。

(1)如果subArray1中元素個數為奇數個，那么對subArray1中的所有數字進行異或操作；由于a^a=0，a^0=a，出現兩次的數字通過異或操作得到的結果為0，然后再與只出現一次的數字執行異或操作，得到的結果就是只出現一次的數字。

(2)如果subArray0中元素個數為奇數個，那么對subArray0中所有元素進行異或操作得到的結果就是其中一個只出現一次的數字。

為了實現上面的思路，必須先找到能區分這三個數字的bit位，根據以上的分析給出本算法的實現思路：

以32位平臺為例，一個int類型的數字占用32位空間，從右向左使用每一位對數組進行分組，分組的過程中，計算這個bit值為0的數字異或的結果result0，出現的次數count0；這個bit值為1的所有數字異或的結果result1，出現的次數count1。

如果count0是奇數且result1!=0，那么說明這三個數中的其中一個被分配到這一bit為0的子數組中了，因此，這個子數組中所有數字異或的值result0一定是出現一次的數字。(如果result1==0，說明這一個bit不能用來區分這三個數字，此時這三個數字都被分配到子數組subArray0中了，因此，result1!=0就可以確定這一個bit可以被用來區分這三個數字的)。

同理，如果count1是奇數且result0!=0，那么result1就是其中一個出現1次的數。

以[6,3,4,5,9,4,3]為例，出現1次的數字為6(110)，5(101)，9(1001)，從右向左第一位就可以區分這三個數字，用這個bit位可以把數字分成兩個子數組subArray0=(6,4,4)和subArray1=(3,5,9,3)。subArray1中所有元素異或的值不等于0，說明出現1次的數字一定在subArray1中出現了，而subArray0中元素個數為奇數個，說明出現1次的數字，其中只有一個被分配到subArray0中了，所以，subArray0中所有元素異或的結果一定就是這個出現1次的數字6。實現代碼如下：

#判斷數字n的二進制數從右往左數第i位是否為1

defisOne(n,i):

return(n&(1＜＜i))==1

deffindSingle(arr):

size=len(arr)

i=0

whilei＜32:

result1=result0=count1=count0=0

j=0

whilej＜size:

ifisOne(arr[j],i):

result1^=arr[j]#第i位為1的值異或操作

count1+=1#第i位為1的數字個數

else:

result0^=arr[j]#第i位為0的值異或操作

count0+=1#第i位為0的值的個數

j+=1

i+=1

"""

bit值為1的予數組元素個數為奇數,且出現1次的數字被分配到bit值為0的子數組,說明只有一個出現1次的數字被分配到bit值為1的予數組中,異或記過就是這個出現一次的數字

"""

ifcount1%2==1andresult0!=0:

returnresult1

#只有一個出現一次的數字被分配到bit值為0的子數組中

ifcount0%2=1andresult1!=0:

returnresult0

return-1

if__name__=="__main__":

arr=[6,3,4,5,9,4,3]

result=findSingle(arr)

ifresult!=-1:

printresult

else:

print"沒找到"

程序的運行結果為：

6

算法性能分析：

這種方法使用了兩層循環，總共循環執行的次數為32*N(N為數組的長度)，因此，算法的時間復雜度為O(N)。[考點]如何找出數組中出現1次的數

2.

請實現方法：print_rotate_matrix(intmatrix,intn)，該方法用于將一個n*n的二維數組逆時針旋轉45°后打印，例如，下圖顯示一個3*3的二維數組及其旋轉后屏幕輸出的效果。

正確答案：本題的思路為：從右上角開始對數組中的元素進行輸出，實現代碼如下：

defrotateArr(arr):

lens=len(arr)

#打印二維數組右上半部分

i=lens-1

whilei＞0:

row=0

col=i

whilecol＜lens:

printarr[row][col],

row+=1

col+=1

print'\n'

i-=1

#打印二維數組左下半部分(包括對角線)

i=0

whilei＜lens:

row=i

col=0

whilerow＜lens:

printarr[row][col],

row+=1

col+=1

print'\n'

i+=1

if__name__="__main__":

arr=[[1,2,3l,[4,5,6l,[7,8,9]]

rotateArr(arr)

程序的運行結果為：

3

26

159

48

7

算法性能分析：

這種方法對數組中的每個元素都遍歷了一次，因此，算法的時間復雜度為O(n2)。[考點]如何對數組旋轉

3.

所謂中位數就是一組數據從小到大排列后中間的那個數字。如果數組長度為偶數，那么中位數的值就是中間兩個數字相加除以2，如果數組長度為奇數，那么中位數的值就是中間那個數字。正確答案：根據定義，如果數組是一個已經排序好的數組，那么直接通過索引即可獲取到所需的中位數。如果題目允許排序的話，那么本題的關鍵在于選取一個合適的排序算法對數組進行排序。一般而言，快速排序的平均時間復雜度較低，為O(NlOg2N)，所以，如果采用排序方法的話，算法的平均時間復雜度為O(Nlog2N)。

可是，題目要求，不許使用排序算法。那么前一種方法顯然走不通。此時，可以換一種思路：分治的思想。快速排序算法在每一次局部遞歸后都保證某個元素左側的元素的值都比它小，右側的元素的值都比它大，因此，可以利用這個思路快速地找到第N大元素，而與快速排序算法不同的是，這種方法關注的并不是元素的左右兩邊，而僅僅是某一邊。

根據快速排序的方法，可以采用一種類似快速排序的方法，找出這個中位數。具體而言，首先把問題轉化為求一列數中第i小的數的問題，求中位數就是求一列數的第(length/2+1)小的數的問題(其中length表示的是數組序列的長度)。

當使用一次類快速排序算法后，分割元素的下標為pos：

(1)當pos＞length/2時，說明中位數在數組左半部分，那么繼續在左半部分查找。

(2)當pos=lengh/2時，說明找到該中位數，返回A[pos]即可。

(3)當pos＜length/2時，說明中位數在數組右半部分，那么繼續在數組右半部分查找。

以上默認此數組序列長度為奇數，如果為偶數就是調用上述方法兩次找到中間的兩個數求平均值。示例代碼如下：

classTest:

def__new__(self):

self.pos=0

#以arr[low]為基準把數組分成兩部分

defpartition(self,arr,low,high):

key=arr[low]

whilelow＜high:

whilelow＜highandarr[high]＞key:

high-=1

arr[low]=arr[high]

whilelow＜highandarr[low]＜key:

low+=1

arr[high]=arr[low]

arr[low]=key

self.pos=low

defgetMid(self,arr):

low=0

n=len(arr)

high=n-1

mid=(low+high)/2

whileTrue:

#以arr[low]為基準把數組分成兩部分

self.partition(arr,low,high)

ifself.pos==mid:#找到中位數

break

elifself.pos＞mid:#繼續在右半部分查找

high=self.pos-1

else:#繼續在左半部分查找

low-self.pos+1

#如果數組長度是奇數,中位數為中間的元素,否則就是中間兩個數的平均值

returnarr[mid]if(n%2)!=0else(arr[mid]+arr[mid+1])/2

if__name__="__main__":

arr=[7,5,3,1,11,9]

printTest().getMid(arr)

程序的運行結果為：

6

算法性能分析：

這種方法在平均情況下的時間復雜度為O(N)。[考點]如何在不排序的情況下求數組中的中位數

4.

有一個集合，求其全部子集(包含集合自身)。給定一個集合s，它包含兩個元素＜a,b＞，則其全部的子集為＜a,ab,b＞。正確答案：根據數學性質分析，不難得知，子集個數Sn與原集合元素個數n之間的關系滿足如下等式：Sn=2^n-1。

方法一：位圖法

具體步驟如下所示。

(1)構造一個和集合一樣大小的數組A，分別與集合中的某個元素對應，數組A中的元素只有兩種狀態：“1”和“0”，分別代表每次子集輸出中集合中對應元素是否要輸出，這樣數組A可以看作是原集合的一個標記位圖。

(2)數組A模擬整數“加1”的操作，每執行“加1”操作之后，就將原集合中所有與數組A中值為“1”的相對應的元素輸出。

設原集合為＜a,b,c,d＞，數組A的某次“加1”后的狀態為[1,0,1,1]，則本次輸出的子集為＜a,c,d＞。使用非遞歸的思想，如果有一個數組，大小為n，那么就使用n位的二進制，如果對應的位為1，那么就輸出這個位，如果對應的位為0，那么就不輸出這個位。

例如集合{a,b,c}的所有子集可表示如下：集合二進制表示{}(空集)000{a}001{b}010{c}100{a,b}011{a,c}101{b,c}110{a,b,c}111

算法的重點是模擬數組加1的操作。數組可以一直加1，直到數組內所有元素都是1。實現代碼如下：

defgetAllSubset(array,mask,c):

length=len(array)

iflength==c:

print"{",

i=0

whilei＜length:

ifmask[i]==1:

printarray[i],

i+=1

print"}"

else:

mask[c]=1

getAllSubset(array,mask,c+1)

mask[c]=0

getAllSubset(array,mask,c+1)

if__name__="__main__":

array=['a,'b','c']

mask=[0,0.0]

getAllSubset(array,mask,0)

程序的運行結果為：

{abc}

{ab}

{ac}

{a}

{bc}

{b}

{c}

該方法的缺點在于如果數組中有重復數時，這種方法將會得到重復的子集。

算法性能分析：

這種方法的時間復雜度為O(N*2N)，空間復雜度O(N)。

方法二、迭代法

采用迭代算法的具體過程如下：

假設原始集合s=＜a,b,c,d＞，子集結果為r：

第一次迭代：

r=＜a＞

第二次迭代：

r=＜aabb＞

第三次迭代：

r=＜aabbacabcbcc＞

第四次迭代：

r=＜aabbacabcbccadabdbdacdabcdbcdcdd＞

每次迭代，都是上一次迭代的結果+上次迭代結果中每個元素都加上當前迭代的元素+當前迭代的元素。

實現代碼如下：

defgetAllSubset(str):

ifstr==Noneorlen(str)＜1:

print"參數不合理"

returnNone

arr=[]

arr.append(str[0:1])

i=1

whilei＜len(str):

lens=len(arr)

j=0

whilej＜lens:

arr.append(arr[j]+str[i])

j+=1

arr.append(str[i:i+1])

i+=1

returnarr

if__name__=="__main__":

result=getAllSubset("abc")

i=0

whilei＜len(result):

printresult[i]

i+=1

程序的運行結果為：

a

ab

b

ac

abc

bc

c

根據上述過程可知，第k次迭代的迭代次數為：2k-1。需要注意的是，n≥k≥1，迭代n次，總的遍歷次數為：2n+1-(2+n)，n≥1，所以，本方法的時間復雜度為O(2n)。

由于在該算法中，下一次迭代過程都需要上一次迭代的結果，而最后一次迭代之后就沒有下一次了。因此，假設原始集合有n個元素，則在迭代過程中，總共需要保存的子集個數為2n-1-1，n≥1。但需要注意的是，這里只考慮了子集的個數，每個子集元素的長度都被視為1。

其實，比較上述兩種方法，不難發現，第一種方法可以看作是用時間換空間，而第二種方法可以看作是用空間換時間。[考點]如何求集合的所有子集

5.

把一個含有N個元素的數組循環右移K(K是正數)位，要求時間復雜度為O(N)，且只允許使用兩個附加變量。正確答案：由于有空間復雜度的要求，因此，只能在原數組中就地進行右移。

方法一：蠻力法

蠻力法也是最簡單的方法，題目中需要將數組元素循環右移K位，只需要每次將數組中的元素右移一位，循環K次即可。例如，假設原數組為abcd1234，那么，按照此種方式，具體移動過程如下所示：abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。

此種方法也很容易寫出代碼。示例代碼如下：

defrightShift(arr,k):

ifarr==None:

print"參數不合法"

return

lens=len(arr)

whilek!=0:

tmp=arr[lens-1]

i=lens-1

whilei＞0:

arr[i]=arr[i-1]

i-=1

arr[0]=tmp

k-=1

if__name__="__main__":

k=4

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

rightShift(arr,k)

i=0

whilei＜len(arr):

printarr[i],

i+=1

程序的運行結果為：

56781234

以上方法雖然可以實現數組的循環右移，但是由于每移動一次，其時間復雜度就為O(N)，所以，移動K次，其總的時間復雜度為0(K*N)，O＜K＜N，與題目要求的O(N)不符合，需要繼續往下探索。

對于上述代碼，需要考慮到，K不一定小于N，有可能等于N，也有可能大于N。當K＞N時，右移K-N之后的數組序列跟右移K位的結果一樣，所以，當K＞N時，右移K位與右移K'(其中K'=K%N)位等價，根據以上分析，相對完備的代碼如下：

defrightshift(arr,k):

ifarr==None:

print"參數不合法"

return

lens=len(arr)

k%=lens

whilek!=0:

t=rr[lens-1];

i=lens-1

whilei＞0:

arr[i]=arr[i-1]

i-=1

arr[0]=t

k-=1

if__name__=="__main__":

k=4;

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

rightShift(arr,k)

i=0

whilei＜len(arr):

priritarr[i],

i+=1

算法性能分析：

上例中，算法的時間復雜度為O(N2)，與K值無關，但時間復雜度仍然太高，是否還有其他更好的方法呢?

仔細分析上面的方法，不難發現，上述方法的移動采取的是一步一步移動的方式，可是問題是，題目中已經告知了需要移動的位數為K，為什么不能一步到位呢?

方法二、空間換時間法

通常情況下，以空間換時間往往能夠降低時間復雜度，本題也不例外。

首先定義一個輔助數組T，把數組A的第N-K+1到N位數組中的元素存儲到輔助數組T中，然后再把數組A中的第1到N-K位數組元素存儲到輔助數組T中，然后將數組T中的元素復制回數組A，這樣就完成了數組的循環右移，此時的時間復雜度O(N)。

雖然時間復雜度滿足要求，但是空間復雜度卻提高了，由于需要創建一個新的數組，所以，此時的空間復雜度O(N)，鑒于此，還可以對此方法繼續優化。

方法三：翻轉法

把數組看成由兩段組成的，記為XY。左旋轉相當于要把數組XY變成YX。先在數組上定義一種翻轉的操作，就是翻轉數組中數字的先后順序。把X翻轉后記為XT。顯然有(XT)T=X。

首先對X和Y兩段分別進行翻轉操作，這樣就能得到XTY