Python程序員面試分類模擬10

Python程序員面試分類模擬10簡(jiǎn)答題1.

給定任意一個(gè)正整數(shù)，求比這個(gè)數(shù)大且最小的“不重復(fù)數(shù)”，“不重復(fù)數(shù)”的含義是相鄰兩位不相同，例如1101是重復(fù)數(shù)，而1201是不重復(fù)數(shù)。正確答案：方法一（江南博哥）：蠻力法

最容易想到的方法就是對(duì)這個(gè)給定的數(shù)加1，然后判斷這個(gè)數(shù)是不是“不重復(fù)數(shù)”，如果不是，那么繼續(xù)加1，直到找到“不重復(fù)數(shù)”為止。顯然這種方法的效率非常低下。

方法二：從右到左的貪心法

例如給定數(shù)字11099，首先對(duì)這個(gè)數(shù)字加1，變?yōu)?1000，接著從右向左找出第一對(duì)重復(fù)的數(shù)字00，對(duì)這個(gè)數(shù)字加1，變?yōu)?1001，繼續(xù)從右向左找出下一對(duì)重復(fù)的數(shù)00，將其加1，同時(shí)把這一位往后的數(shù)字變?yōu)?101…串(當(dāng)某個(gè)數(shù)字自增后，只有把后面的數(shù)字變成0101…，才是最小的不重復(fù)數(shù)字)，這個(gè)數(shù)字變?yōu)?1010，接著采用同樣的方法，11010-＞12010就可以得到滿足條件的數(shù)。

需要特別注意的是當(dāng)對(duì)第i個(gè)數(shù)進(jìn)行加1操作后可能會(huì)導(dǎo)致第i個(gè)數(shù)與第i+1個(gè)數(shù)相等，因此，需要處理這種特殊情況，下圖以99020為例介紹處理方法。

(1)把數(shù)字加1并轉(zhuǎn)換為字符串。

(2)從右到左找到第一組重復(fù)的數(shù)99(數(shù)組下標(biāo)為i=2)，然后把99加1，變?yōu)?00，然后把后面的字符變?yōu)?101…串。得到100010。

(3)由于執(zhí)行步驟(2)后對(duì)下標(biāo)為2的值進(jìn)行了修改，導(dǎo)致它與下標(biāo)為i=3的值相同，因此，需要對(duì)i自增變?yōu)閕=3，接著從i=3開始從右向左找出下一組重復(fù)的數(shù)字00，對(duì)00加1變?yōu)?1，后面的字符變?yōu)?101…串，得到100101。

(4)由于下標(biāo)為i=3與i+1=4的值不同，因此，可以從i-1=2的位置開始從右向左找出下一組重復(fù)的數(shù)字00，對(duì)其加1就可以得到滿足條件的最小的“不重復(fù)數(shù)”。

根據(jù)這個(gè)思路給出實(shí)現(xiàn)方法如下：

1)對(duì)給定的數(shù)加1。

2)循環(huán)執(zhí)行如下操作：對(duì)給定的數(shù)從右向左找出第一對(duì)重復(fù)的數(shù)(下標(biāo)為i)，對(duì)這個(gè)數(shù)字加1，然后把這個(gè)數(shù)字后面的數(shù)變?yōu)?101…得到新的數(shù)。如果操作結(jié)束后下標(biāo)為i的值等于下標(biāo)為i+1的值，那么對(duì)i進(jìn)行自增，否則對(duì)i進(jìn)行自減；然后從下標(biāo)為i開始從右向左重復(fù)執(zhí)行步驟2)，直到這個(gè)數(shù)是“不重復(fù)數(shù)”為止。

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

"""

方法功能:處理數(shù)字相加的進(jìn)位

輸入?yún)?shù):num為字符數(shù)組,pos為進(jìn)行加1操作對(duì)應(yīng)的下標(biāo)位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

num[pos-1]=str(int(num[pos-1])+1)

pos-=1

"""

方法功能:獲取大于n的最小不重復(fù)數(shù)

輸入?yún)?shù):n為正整數(shù)

返回值:大于n的最小不重復(fù)數(shù)

"""

deffindMinNonDupNum(n):

count=0#用來記錄循環(huán)次數(shù)

nChar=list(str(n+1))

ch=[None]*(len(nChar)+2)

ch[0]='0'

ch[len(ch)-1]='0'

i=0

whilei＜len(nChar):

ch[i+1]=nChar[i]

i+=1

lens=len(ch)

i=lens-2#從右向左遍歷

whilei＞0:

count+=1

ifch[i-1]==ch[i]:

ch[i]=str(int(ch[i])+1)#末尾數(shù)字加1

carry(ch,i)#處理進(jìn)位

#把下標(biāo)為i后面的字符串變?yōu)?101…串

j=i+1

whilej＜lens:

if(j-i)%2==1:

ch[j]=0'

else:

ch[j]='1'

j+=1

#第i位加1后,可能會(huì)與第i+1位相等

i+=1

else:

i-=1

print"循環(huán)次數(shù)為:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

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

循環(huán)次數(shù)為：7

23401

循環(huán)次數(shù)為：11

1201010

循環(huán)次數(shù)為：13

101010

循環(huán)次數(shù)為：10

9010

方法三：從左到右的貪心法

與方法二類似，只不過是從左到右開始遍歷，如果碰到重復(fù)的數(shù)字，那么把其加1，后面的數(shù)字變成0101…串。實(shí)現(xiàn)代碼如下：

"""

方法功能:處理數(shù)字相加的進(jìn)位

輸入?yún)?shù):num為字符數(shù)組,pos為進(jìn)行加1操作對(duì)應(yīng)的下標(biāo)位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

num[pos-1]=str(int(num[pos-1])+1)

pos-=1

"""

方法功能:獲取大于n的最小不重復(fù)數(shù)

輸入?yún)?shù):n為正整數(shù)

返回值:大于n的最小不重復(fù)數(shù)

"""

deffindMinNonDupNum(n):

count=0#用來記錄循環(huán)次數(shù)

nChar=list(str(n+1))

ch=[None]*(len(nChar)+1)

ch[0]='0'

i=0

whilei＜len(nChar):

ch[i+1]=nChar[i]

i+=1

lens=len(ch)

i=2#從左向右遍歷

whilei＜lens:

count+=1

ifch[i-1]==ch[i]:

ch[i]=str(int(ch[i])+1)#末尾數(shù)字加1

carry(ch,i)#處理進(jìn)位

#把下標(biāo)為i后面的字符串變?yōu)?101...串

j=i+1

whilej＜lens:

if(j-i)%2==1:

ch[j]='0'

else:

ch[j]='1'

j+=1

else:

i+=1

print"循環(huán)次數(shù)為:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

顯然，方法三循環(huán)的次數(shù)少于方法二，因此，方法三的性能要優(yōu)于方法二。[考點(diǎn)]如何找最小的不重復(fù)數(shù)

2.

給定一個(gè)帶頭結(jié)點(diǎn)的單鏈表，請(qǐng)將其逆序。即如果單鏈表原來為head-＞1-＞2-＞3-＞4-＞5-＞6-＞7，那么逆序后變?yōu)閔ead-＞7-＞6-＞5-＞4-＞3-＞2-＞1。正確答案：由于單鏈表與數(shù)組不同，單鏈表中每個(gè)結(jié)點(diǎn)的地址都存儲(chǔ)在其前驅(qū)結(jié)點(diǎn)的指針域中，因此，對(duì)單鏈表中任何一個(gè)結(jié)點(diǎn)的訪問只能從鏈表的頭指針開始進(jìn)行遍歷。在對(duì)鏈表的操作過程中，需要特別注意在修改結(jié)點(diǎn)指針域的時(shí)候，記錄下后繼結(jié)點(diǎn)的地址，否則會(huì)丟失后繼結(jié)點(diǎn)。

方法一：就地逆序

主要思路為：在遍歷鏈表的時(shí)候，修改當(dāng)前結(jié)點(diǎn)的指針域的指向，讓其指向它的前驅(qū)結(jié)點(diǎn)。為此需要用一個(gè)指針變量來保存前驅(qū)結(jié)點(diǎn)的地址。此外，為了在調(diào)整當(dāng)前結(jié)點(diǎn)指針域的指向后還能找到后繼結(jié)點(diǎn)，還需要另外一個(gè)指針變量來保存后繼結(jié)點(diǎn)的地址，在所有的結(jié)點(diǎn)都被保存好以后就可以直接完成指針的逆序了。除此之外，還需要特別注意對(duì)鏈表首尾結(jié)點(diǎn)的特殊處理。具體實(shí)現(xiàn)方式如下圖所示。

在上圖中，假設(shè)當(dāng)前已經(jīng)遍歷到cur結(jié)點(diǎn)，由于它所有的前驅(qū)結(jié)點(diǎn)都已經(jīng)完成了逆序操作，因此，只需要使cur.next=pre即可完成逆序操作，在此之前，為了能夠記錄當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址，需要用一個(gè)額外的指針next來保存后繼結(jié)點(diǎn)的信息，通過上圖(1)～(4)四步把實(shí)線的指針調(diào)整為虛線的指針就可以完成當(dāng)前結(jié)點(diǎn)的逆序。當(dāng)前結(jié)點(diǎn)完成逆序后，通過向后移動(dòng)指針來對(duì)后續(xù)的結(jié)點(diǎn)用同樣的方法進(jìn)行逆序操作。算法實(shí)現(xiàn)如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#方法功能:對(duì)單鏈表進(jìn)行逆序輸入?yún)?shù):head:鏈表頭結(jié)點(diǎn)

defReverse(head):

#判斷鏈表是否為空

ifhead==Noneorhead.next==None:

return

pre=None#前驅(qū)結(jié)點(diǎn)

cur=None#當(dāng)前結(jié)點(diǎn)

next=None#后繼結(jié)點(diǎn)

#把鏈表首結(jié)點(diǎn)變?yōu)槲步Y(jié)點(diǎn)

cur=head.next

next=cur.next

cur.next=None

pre=cur

cur=next

#使當(dāng)前遍歷到的結(jié)點(diǎn)cur指向其前驅(qū)結(jié)點(diǎn)

whilecur.next!=Node:

next=cur.next

cur.next=pre

pre=cur

cur=cur.next

cur=next

#鏈表最后一個(gè)結(jié)點(diǎn)指向倒數(shù)第二個(gè)結(jié)點(diǎn)

cur.next=pre

#鏈表的頭結(jié)點(diǎn)指向原來鏈表的尾結(jié)點(diǎn)

head.next=cur

if__name__=="__main__".

i=1

#鏈表頭結(jié)點(diǎn)

head=LNode()

head.next=None

tmp=None

cur=head

#構(gòu)造單鏈表

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"逆序前:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

print"\n逆序后:",

Reverse(head)

cur=head.next

whilecur!=None:

printcur.data,

Cur=cur.next

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

逆序前：1234567

逆序后：7654321

算法性能分析：

以上這種方法只需要對(duì)鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(N)，其中，N為鏈表的長(zhǎng)度。但是需要常數(shù)個(gè)額外的變量來保存當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)與后繼結(jié)點(diǎn)，因此，空間復(fù)雜度為O(1)。

方法二：遞歸法

假定原鏈表為1-＞2-＞3-＞4-＞5-＞6-＞7，遞歸法的主要思路為：先逆序除第一個(gè)結(jié)點(diǎn)以外的子鏈表(將1-＞2-＞3-＞4-＞5-＞6-＞7變?yōu)?-＞7-＞6-＞5-＞4-＞3-＞2)，接著把結(jié)點(diǎn)1添加到逆序的子鏈表的后面(1-＞7-＞6-＞5-＞4-＞3-＞2變?yōu)?-＞6-＞5-＞4-＞3-＞2-＞1)。同理，在逆序鏈表2-＞3-＞4-＞5-＞6-＞7時(shí)，也是先逆序子鏈表3-＞4-＞5-＞6-＞7(逆序?yàn)?-＞7-＞6-＞5-＞4-＞3)，接著實(shí)現(xiàn)鏈表的整體逆序(2-＞7-＞6-＞5-＞4-＞3轉(zhuǎn)換為7-＞6-＞5-＞4-＞3-＞2)。實(shí)現(xiàn)代碼如下：

"""

方法功能:對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行逆序

輸入?yún)?shù):firstRef:鏈表頭結(jié)點(diǎn)

"""

defRecursiveReverse(head):

#如果鏈表為空或者鏈表中只有一個(gè)元素

ifheadisNoneorhead.nextisNone:

returnhead

else:

#反轉(zhuǎn)后面的結(jié)點(diǎn)

newhead=RecursiveReverse(head.next)

#把當(dāng)前遍歷的結(jié)點(diǎn)加到后面結(jié)點(diǎn)逆序后鏈表的尾部

head.next.next=head

head.next=None

returnnewhead

"""

方法功能:對(duì)帶頭結(jié)點(diǎn)的單鏈表進(jìn)行逆序

輸入?yún)?shù):head:鏈表頭結(jié)點(diǎn)

"""

defReverse(head):

ifheadisNone:

return

#獲取鏈表第一個(gè)結(jié)點(diǎn)

firstNode=head.next

#對(duì)鏈表進(jìn)行逆序

newhead=RecursiveReverse(firstNode)

#頭結(jié)點(diǎn)指向逆序后鏈表的第一個(gè)結(jié)點(diǎn)

head.next=newhead

returnnewhead

算法性能分析：

由于遞歸法也只需要對(duì)鏈表進(jìn)行一次遍歷，因此，算法的時(shí)間復(fù)雜度也為O(N)，其中，N為鏈表的長(zhǎng)度。遞歸法的主要優(yōu)點(diǎn)是：思路比較直觀，容易理解，而且也不需要保存前驅(qū)結(jié)點(diǎn)的地址。缺點(diǎn)是：算法實(shí)現(xiàn)的難度較大，此外，由于遞歸法需要不斷地調(diào)用自己，需要額外的壓棧與彈棧操作，因此，與方法一相比性能會(huì)有所下降。

方法三：插入法

插入法的主要思路為：從鏈表的第二個(gè)結(jié)點(diǎn)開始，把遍歷到的結(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面，直到遍歷結(jié)束。假定原鏈表為head-＞1＞2-＞3-＞4-＞5-＞6-＞7，在遍歷到2的時(shí)候，將其插入到頭結(jié)點(diǎn)后，鏈表變?yōu)閔ead-＞2-＞1＞3-＞4-＞5-＞6-＞7，同理將后序遍歷到的所有結(jié)點(diǎn)都插入到頭結(jié)點(diǎn)head后，就可以實(shí)現(xiàn)鏈表的逆序。實(shí)現(xiàn)代碼如下：

defReverse(head):

#判斷鏈表是否為空

ifheadisNoneorhead.nextisNone:

return

cur=None#當(dāng)前結(jié)點(diǎn)

next=None#后繼結(jié)點(diǎn)

cur=head.next.next

#設(shè)置鏈表第一個(gè)結(jié)點(diǎn)為尾結(jié)點(diǎn)

head.next.next=None

#把遍歷到結(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面

whilecurisnotNone:

next=cur.next

cur.next=head.next

head.next=cur

cur=next

算法性能分析：

以上這種方法也只需要對(duì)單鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(N)，其中，N為鏈表的長(zhǎng)度。與方法一相比，這種方法不需要保存前驅(qū)結(jié)點(diǎn)的地址，與方法二相比，這種方法不需要遞歸地調(diào)用，效率更高。[考點(diǎn)]如何實(shí)現(xiàn)鏈表的逆序

3.

請(qǐng)?jiān)O(shè)計(jì)一個(gè)排隊(duì)系統(tǒng)，能夠讓每個(gè)進(jìn)入隊(duì)伍的用戶都能看到自己在隊(duì)列中所處的位置和變化，隊(duì)伍可能隨時(shí)有人加入和退出；當(dāng)有人退出影響到用戶的位置排名時(shí)需要及時(shí)反饋到用戶。正確答案：本題不僅要實(shí)現(xiàn)隊(duì)列常見的入隊(duì)列與出隊(duì)列的功能，而且還需要實(shí)現(xiàn)隊(duì)列中任意一個(gè)元素都可以隨時(shí)出隊(duì)列，且出隊(duì)列后需要更新隊(duì)列用戶位置的變化。實(shí)現(xiàn)代碼如下：

fromcollectionsimportdeque

classUser:

def__init__(self,id,name):

self.id=id#唯一標(biāo)識(shí)一個(gè)用戶

=name

self.seq=0

defgetName(self):

return

defsetName(self,name):

=name

defgetSeq(self):

returnself.seq

defsetSeq(self,seq):

self.seq=seq

defgetId(self):

returnself.id

defequals(self,arg0):

o=arg0

returnself.id=o.getId()

deftoString(self):

return"id:"+str(self.id)+"name:"++"seq:"+str(self.seq)

classMyQueue:

def__init__(self):

self.q=deque()

defenQueue(self,u):#進(jìn)入隊(duì)列尾部

u.setSeq(len(self.q)+1)

self.q.append(u)

#隊(duì)頭出隊(duì)列

defdeQueue(self):

self.q.popleft()

self.updateSeq()

#隊(duì)列中的人隨機(jī)離開

defdeQueuemove(self,u):

self.q.remove(u)

self.updateSeq()

#出隊(duì)列后更新隊(duì)列中每個(gè)人的序列

defupdateSeq(self):

i=1

foruinself.q:

u.setSeq(i)

i+=1

#打印隊(duì)列的信息

defprintList(self):

foruinself.q:

printu.toString()

if__name__=="__main__":

u1=User(1,"user1")

u2=User(2,"user2")

u3=User(3,"user3")

u4=User(4,"user4")

queue=MyQueue()

queue.enQueue(u1)

queue.enQueue(u2)

queue.enQueue(u3)

queue.enQueue(u4)

queue.deQueue()#隊(duì)首元素u1出隊(duì)列

queue.deQueuemove(u3)#隊(duì)列中間的元素u3出隊(duì)列

queue.printList()

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

id:2name:user2seq:1

id:4name:user4seq:2[考點(diǎn)]如何設(shè)計(jì)一個(gè)排序系統(tǒng)

4.

有N個(gè)磁盤，每個(gè)磁盤大小為D[i](i=0...N-1)，現(xiàn)在要在這N個(gè)磁盤上”順序分配”M個(gè)分區(qū)，每個(gè)分區(qū)大小為P[j](j=0…M-1)，順序分配的意思是：分配一個(gè)分區(qū)P[j]時(shí)，如果當(dāng)前磁盤剩余空間足夠，則在當(dāng)前磁盤分配；如果不夠，則嘗試下一個(gè)磁盤，直到找到一個(gè)磁盤D[i+k]可以容納該分區(qū)，分配下一個(gè)分區(qū)P[j+1]時(shí)，則從當(dāng)前磁盤D[i+k]的剩余空間開始分配，不在使用D[i+k]之前磁盤末分配的空間，如果這M個(gè)分區(qū)不能在這N個(gè)磁盤完全分配，則認(rèn)為分配失敗，請(qǐng)實(shí)現(xiàn)函數(shù)，isallocable判斷給定N個(gè)磁盤(數(shù)組D)和M個(gè)分區(qū)(數(shù)組P)，是否會(huì)出現(xiàn)分配失敗的情況?舉例：磁盤為[120,120,120]，分區(qū)為[60,60,80,20,80]可分配，如果為[60,80,80,20,80]，則分配失敗。正確答案：本題的主要思路如下：對(duì)所有的分區(qū)進(jìn)行遍歷，同時(shí)用一個(gè)變量dIndex記錄上次分配磁盤的下標(biāo)，初始化為0；對(duì)于每個(gè)分區(qū)，從上次分配的磁盤開始繼續(xù)分配，如果沒有足夠的空間，則順序找其他的磁盤，直到找到合適的磁盤為止，進(jìn)行分配；如果找不到合適的磁盤，則分配失敗，實(shí)現(xiàn)代碼如下：

defis_allocable(d,p):

dIndex=0#磁盤分區(qū)下標(biāo)

i=0

whilei＜len(p):

#找到符合條件的磁盤

whiledIndex＜len(d)andp[i]＞d[dIndex]:

dIndex+=1

#沒有可用的磁盤

ifdIndex＞=len(d):

returnFalse

#給分區(qū)分配磁盤

d[dIndex]-=p[i]

i+=1

returnTrue

if__name__=="__main__":

d=[120,120,120]#磁盤

p=[60,60,80,20,80]#分區(qū)

ifis_allocable(d,p):

print"分配成功"

else:

print"分配失敗"

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

分配成功

算法性能分析：

這種方法使用了雙重循環(huán)，因此，時(shí)間復(fù)雜度為O(MN)。[考點(diǎn)]如何對(duì)磁盤分區(qū)

5.

把一個(gè)有序數(shù)組最開始的若干個(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。正確答案：Python中可以使用列表來表示有序數(shù)組，因此示例中都用列表來表示有序數(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)單的方法就是直接遍歷法。但是這種方法顯然沒有用到題目中旋轉(zhuǎn)數(shù)組的特性，因此，它的效率比較低下，下面介紹一種比較高效的二分查找法。

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

(1)數(shù)組本身是沒有發(fā)生過旋轉(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]。

通過旋轉(zhuǎn)數(shù)組的定義可知，經(jīng)過旋轉(zhuǎn)之后的數(shù)組實(shí)際上可以劃分為兩個(gè)有序的子數(shù)組，前面的子數(shù)組的元素值都大于或者等于后面子數(shù)組的元素值。可以根據(jù)數(shù)組元素的這個(gè)特點(diǎ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，即沒有旋轉(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í)無法區(qū)分最小值是在數(shù)組的左半部分還是右半部分(例如：[2,2,2,2,1,2]，[2,1,2,2,2,2,2])。在這種情況下，只能分別在數(shù)組的左右兩部分找最小值minL與minR，最后求出minL與minR的最小值。

示例代碼如下：