劍指offer：旋轉數組的最小數字（Python）

題目描述

把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請傳回0。

解題思路

思路1

暴力解法：根據給定的數組特點，從左到右周遊數組元素，當首次遇到數組中某個元素比上一個元素小時，該元素就是我們需要的元素。

python代碼

defminNumberInRotateArray(self, rotateArray):
    if not rotateArray:
        return 
    num = rotateArray[]
    for i in range(,len(rotateArray)):
        if rotateArray[i] >= num:
            num = rotateArray[i]
        else:
            return rotateArray[i]
           

思路2

思路1的做法太無腦，時間複雜度O(N)。旋轉數組也算是一種排序數組，可以用二分法解題，使時間複雜度最低控制在O(lgN)。

由于最近遞歸用的比較多，本能的就想通過遞歸求解該題。具體思路是用變量mid定位到數組的中間位置，将數組頭部的值與mid處的值進行比較，不斷縮小數組。這裡有兩個需要注意的點：

1. 由于是旋轉數組，縮小到最小的數組大小為2，且數組中第一個元素為數組中值最大的元素，第二個元素是數組中值最小的元素，最後傳回第二個元素。

2. 當數組中包含重複元素，具體到代碼中是：當mid處的值等于數組頭部的值時，無法判斷最小值位于mid左側還是右側，此時隻能采取周遊的方式。

Python代碼

def minNumberInRotateArray(self, rotateArray):
    if not rotateArray:
        return 
    if len(rotateArray)==:
        return rotateArray[]

    mid = int(len(rotateArray)/)
    if rotateArray[mid] > rotateArray[]:
        return self.minNumberInRotateArray(rotateArray[mid:])
    elif rotateArray[mid] < rotateArray[]:
        return self.minNumberInRotateArray(rotateArray[:mid+])
    else:
        for i in range(,len(rotateArray)):
            if rotateArray[i] < rotateArray[]:
                return rotateArray[i]
        return rotateArray[]
           

思路3

思路3屬于思路2的小優化，可以縮短代碼的長度，但不能改變代碼的時間複雜度。具體來說，當mid處的值等于數組頭部的值時，即當代碼需要周遊時，可用一行代碼代替for循環：

def minNumberInRotateArray(self, rotateArray):
    if not rotateArray:
        return 
    if len(rotateArray)==:
        return rotateArray[]

    mid = int(len(rotateArray)/)
    if rotateArray[mid] > rotateArray[]:
        return self.minNumberInRotateArray(rotateArray[mid:])
    elif rotateArray[mid] < rotateArray[]:
        return self.minNumberInRotateArray(rotateArray[:mid+])
    else:
        return self.minNumberInRotateArray(rotateArray[:])
           

思路4

由于每次遞歸都需要傳入數組，這無疑更占用存儲空間，特别當數組特别長時。最後給出該方法的非遞歸版本，隻有一個數組不變，變化的隻有指向數組的指針指向。

def minNumberInRotateArray(self, rotateArray):
    left = 
    right = len(rotateArray)-
    while left < right:
        mid = int((left+right)/)
        if rotateArray[mid] > rotateArray[right]:
            left = mid+
        elif rotateArray[mid] < rotateArray[right]:
            right = mid
        else:
            right -= 
    return rotateArray[left]
           

雖然思路4代碼簡短，時間複雜度和空間複雜度都比較低，但是如果稍微不注意，還是會掉到小坑裡，比如如果用mid處的值和數組左邊的值比較，會有什麼不同；else語句中如果不讓right處的指向左移一位，而是讓left處的指針右移一位會怎麼樣，都是需要稍加留意的地方。