題目描述

把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。

示例

示例 1：

輸入：[3,4,5,1,2]
輸出：1

示例2：

輸入：[2,2,2,0,1]
輸出：0

解答方法

方法一：二分法

思路

• 循環(huán)二分： 設(shè)置 left,right指針?lè)謩e指向 numbers 數(shù)組左右兩端，m = (left + right) // 2為每次二分的中點(diǎn)（ "http://" 代表向下取整除法，因此恒有），可分為以下三種情況：
  當(dāng) numbers[m] > numbers[right]時(shí)： m 一定在 左排序數(shù)組 中，即最小值 x 一定在 [m + 1,right]閉區(qū)間內(nèi)，因此執(zhí)行l(wèi)eft=m+1；
  當(dāng) numbers[m] < numbers[right] 時(shí)： m一定在 右排序數(shù)組 中，即最小值x 一定在[left, m]閉區(qū)間內(nèi)，因此執(zhí)行right=m；
  當(dāng) numbers[m] == numbers[right] 時(shí)： 無(wú)法判斷m 在哪個(gè)排序數(shù)組中，即無(wú)法判斷旋轉(zhuǎn)點(diǎn) x 在 [left, m] 還是 [m+1,right] 區(qū)間中。解決方案： 執(zhí)行right=right?1 縮小判斷范圍 （分析見(jiàn)以下內(nèi)容） 。
• 返回值： 當(dāng) left = right時(shí)跳出二分循環(huán)，并返回 numbers[left] 即可。
  參考：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/

代碼

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if len(numbers) == 0:
            return
        left = 0
        right = len(numbers)-1
        while left<right:
            mid = left + (right-left)//2
            if numbers[mid] > numbers[right]:
                left = mid + 1
            elif numbers[mid] < numbers[right]:
                right = mid
            else: 
                right -= 1
        return numbers[left]

時(shí)間復(fù)雜度

O(log N) ： 在特例情況下（例如 [1, 1, 1, 1]），會(huì)退化到 O(N)。

空間復(fù)雜度

O(1) ：left , right , mid 指針使用常數(shù)大小的額外空間。