154.尋找旋轉排序數組中的最小值 II
描述
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如,數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
請找出其中最小的元素。
注意數組中可能存在重複的元素。
示例
示例 1:
輸入: [1,3,5]
輸出: 1
示例 2:
輸入: [2,2,2,0,1]
輸出: 0
思路
這題跟上題唯一的差別在于元素可能有重複, 我們仍然采用上面的方法, 隻是需要處理 mid 與 start 相等這種額外情況。
- A[mid] > A[start], 右半區間查找。
- A[mid] < A[start], 左半區間查找。
- A[mid] = A[start], 出現這種情況, 我們跳過 start, 重新查找, 譬如 [2,2,2,1], A[mid] = A[start]都為 2,這時候我們跳過 start, 使用 [2,2,1] 繼續查找。
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
len_nums = len(nums)
if len_nums == 0:
return 0
elif len_nums == 1:
return nums[0]
elif len_nums == 2:
return min(nums[0], nums[1])
start = 0
stop = len_nums - 1
while start < stop - 1:
if nums[start] < nums[stop]:
return nums[start]
mid = start + (stop - start) // 2
if nums[mid] > nums[start]:
start = mid
elif nums[mid] < nums[start]:
stop = mid
else:
start += 1
return min(nums[start], nums[stop])
GitHub位址:https://github.com/protea-ban/LeetCode
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL1QzN5QTNzcDOtEjNyIDM5QTOwEDM1ATOxAjMtczN5EDM38CX1ATOxAjMvw1N3kTMwczLcd2bsJ2Lc12bj5ycn9Gbi52YugTMwIzZtl2Lc9CX6MHc0RHaiojIsJye.png)
轉載于:https://www.cnblogs.com/banshaohuan/p/9758786.html