解题思路
思路与上一题相同
唯一例外就是选取的中点可能与两个端点都相等,这时两边都要见检查
154. 寻找旋转排序数组中的最小值 II
代码
class Solution:
def findMin(self, nums: List[int]) -> int:
return findmin(nums, 0, len(nums)-1)
def findmin(arr, low, high):
if low == high: return arr[low]
if arr[low] < arr[high]: return arr[low]
mid = (low + high) // 2
if arr[low] < arr[mid]:
return findmin(arr, mid+1, high)
if arr[low] > arr[mid]:
return findmin(arr, low, mid)
if arr[mid] < arr[high]:
return findmin(arr, low, mid)
if arr[mid] > arr[high]:
return findmin(arr, mid+1, high)
# arr[low] == arr[mid] == arr[high]
return min(findmin(arr, low, mid), findmin(arr, mid+1, high))
![](https://img.haomeiwen.com/i4291429/74f4c0f8f233873e.png)
网友评论