劍指offer 11 旋轉數組的最小數字

leetcode 刷題 ——劍指offer 11 旋轉數組的最小數字@TOC

把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如，數組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該數組的最小值為1。

示例 1：

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

輸出：1

示例 2：

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

輸出：0

我最先想到的方式：暴力比較

對比兩個list中的元素，一旦出現前一個大于後一個的情況，那後一個就是被旋轉的最小值。因為遞增清單旋轉之後隻會出現兩段遞增清單。（最後加上沒有旋轉過的清單的情況）

python：

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        n = len(numbers)

        for i in range(n-1):
            if numbers[i]>numbers[i+1]:
                return numbers[i+1]
        return numbers[0]
           

官方題解使用了二分查找

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

作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-by-leetcode-s/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。