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

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

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

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

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

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

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

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

        return rotateArray[mid]

網(wǎng)站欄目：劍指offer：旋轉(zhuǎn)數(shù)組的最小值
當(dāng)前鏈接：http://chinadenli.net/article32/gjospc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、網(wǎng)站排名、軟件開發(fā)、ChatGPT、Google、靜態(tài)網(wǎng)站

廣告

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