题目描述：

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.

题目大意：

假设一个排好序的数组在某处执行了一次“旋转”，找出最小的元素（数组元素可能重复）

此题目为"Find Minimum in Rotated Sorted Array"的扩展（去掉了数组不重复的限制条件）

可能出错的测试样例：[3,3,1,3]，[10,1,10,10,10]

解题思路：

线性枚举（ 复杂度O(n) ），二分法（ 最坏复杂度O(n) ，当输入数据为n个相同的数时 ），实测数据比较水。

Python代码：

二分法（20160523增补，感谢网友null122补充）：

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)

本文链接：http://bookshadow.com/weblog/2014/11/06/find-minimum-in-rotated-sorted-array-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码