Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array 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.
follow up,和一主要的不同在于有重复数字。当
class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 l = 0 r = len(nums) - 1 while l + 1 < r: mid = l + (r - l)/2 if nums[mid] == nums[r]: ＃只用移动一位就可以。 r -= 1 elif nums[mid] > nums[r]: l = mid else: r = mid return min(nums[l], nums[r])
Find Minimum in Rotated Sorted Array II
原文：http://www.cnblogs.com/sherylwang/p/5674910.html