原題鏈接https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
本題主要是會出現(xiàn)一些特殊情況圆雁，比如
1.[1,2,3,4,5]未發(fā)生翻轉(zhuǎn)的情況
2.[1,1,1,1,1,1]數(shù)字全部一樣
3.[1,1,1,1,0,1,1,1]數(shù)字大部分相等
本題思路是倒槐，通過對首尾元素的比較結(jié)果進(jìn)行分類闸氮。
若arr[low] == arr[high]，則此時(shí)大概率是二分法下最壞情況展辞，此時(shí)二分法的時(shí)間復(fù)雜度為O(N),所以直接采用順序比較。（偷個(gè)小懶，更優(yōu)解法二刷再說）
若arr[low] < arr[high],則最小元素為首位元素金吗。
若arr[low] >arr[high],則采用二分法。
class Solution:
def findMin(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:return 0
if n == 1:return nums[0]
def get_min(arr,low,high):
mid = low + ((high - low) >> 1)
if arr[mid] > arr[mid + 1]:
return arr[mid + 1]
elif arr[mid] < arr[mid - 1]:
return arr[mid]
elif arr[high] > arr[mid] or arr[low] > arr[mid]:
return get_min(arr,low, mid-1)
elif arr[low] < arr[mid] or arr[high] < arr[mid]:
return get_min(arr,mid+1, high)
if nums[0] < nums[n-1]:
return nums[0]
elif nums[0] > nums[n-1]:
return get_min(nums, 0, n-1)
else:
mins = float('inf')
for num in nums:
if num < mins:
mins = num
return mins
