154. Find Minimum in Rotated Sorted Array II
这题是一道followup的问题,解法只是普通的二分法,只是如果有重复元素的时候,最坏的情况是 O(n)达不到log(n)的情况了
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return None
if len(nums) == 1:
return nums[0]
if nums[0] < nums[-1]:
return nums[0]
start = 0
end = len(nums) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] > nums[end]:
start = mid
elif nums[mid] < nums[end]:
end = mid
else:
end -= 1
if nums[start] > nums[end]:
return nums[end]
else:
return nums[start]