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

成都網站建設哪家好，找創新互聯！專注于網頁設計、重慶網站建設、微信開發、小程序開發、集團成都企業網站定制等服務項目。核心團隊均擁有互聯網行業多年經驗，服務眾多知名企業客戶；涵蓋的客戶類型包括：花箱等眾多領域，積累了大量豐富的經驗，同時也獲得了客戶的一致贊美！

class Solution:
    """
    由于整個數組在一定程度上是有序的，因此可以借鑒二分查找的思想，達到接近O(logn)的時間復雜度。
    將一個有序(升序)數組的前x個元素挪到末尾，這里可以分類進行討論。

    第一類：挪動元素個數為數組長度的整數倍，那么這時候等于沒有挪動，最小值出現在idx=0
    第二類：挪動元素個數不是數組長度的整數倍，那么這時候挪動后的數組可以分成兩個子數組，其中左邊子
          數組的元素都是大于等于右邊子數組的。
          [3, 4, 5, 1, 2]
          這時候我們維護兩個指針p1和p2，分別指向左邊子數組和右邊子數組。當中間元素大于等于p1指向
          的元素的時候，則中間元素屬于左邊子數組，反之屬于右邊子數組。
          當兩個指針相鄰的時候p2就指向了右邊子數組的第一個元素，也就是整個數組的最小值。
    第三類：[1, 0, 1, 1, 1]
          當p1和p2指向的元素和中間的元素相等的時候，這時候如果按照第二類的思路，那么會誤判最小值
          在中間元素之后，因此這種情況下我們需要順序查找。
    """
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0

        # 將mid初始化為0，可以處理第一類情況，因為這時不會進入循環，直接輸出最小值
        left, mid, right = 0, 0, len(rotateArray) - 1

        while rotateArray[left] >= rotateArray[right]:
            # 如果left和right已經相鄰，那么最小值就是right指向的元素
            if left == right - 1:
                mid = right
                break

            mid = (left + right) >> 1
            # 如果left, right, mid指向的元素都相等，那么需要對這個區間進行順序查找，否則按照
            # 第二類情況的解題思路會判斷錯誤
            if rotateArray[left] == rotateArray[mid] == rotateArray[right]:
                return min(rotateArray[left:right + 1])

            # 中間元素在左半邊，最小值出現在右邊子數組[mid, right]
            if rotateArray[left] <= rotateArray[mid]:
                left = mid
            # 中間元素在右半邊，最小值出現在左邊子數組[left, mid]
            else:
                right = mid

        return rotateArray[mid]

網站欄目：劍指offer：旋轉數組的最小值
當前鏈接：http://vcdvsql.cn/article32/gjospc.html

成都網站建設公司_創新互聯，為您提供網站建設、網站排名、軟件開發、ChatGPT、Google、靜態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯