题目描述：

LeetCode 154. Find Minimum in Rotated Sorted Array II

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.

Python代码：

``````class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) / 2
if nums[mid] < nums[right]:
right = mid
elif nums[mid] > nums[right]:
left = mid + 1
else:
return min(self.findMin(nums[:mid+1]), self.findMin(nums[mid+1:]))
return nums[left]
``````

``````class Solution:
# @param num, a list of integer
# @return an integer
def findMin(self, num):
ans = num[0]
size = len(num)
low, high = 0, size - 1
while low <= high:
mid = (low + high) / 2
ans = min(ans, num[mid])
if num[mid] < num[high]: #min位于上升沿左侧
high = mid - 1
elif num[mid] > num[high]: #min位于左侧上升沿与右侧上升沿之间
low = mid + 1
else: #num[mid] == num[high]
if low < mid:
ans = min(ans, self.findMin( num[low : mid + 1] ))
if mid + 1 < high:
ans = min(ans, self.findMin( num[mid + 1 : high + 1] ))
break
return ans
``````

``````class Solution:
# @param num, a list of integer
# @return an integer
def findMin(self, num):
return min(num)
``````

Pingbacks已关闭。