170 - 154 寻找旋转排序数组中的最小值2 - 006

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [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

说明：

• 这道题是 寻找旋转排序数组中的最小值 的延伸题目。

• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

解答

二分法

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/154-find-minimum-in-rotated-sorted-array-ii-by-jyd/

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/er-fen-fa-fen-zhi-fa-python-dai-ma-by-liweiwei1419/

关键就是如果nums[mid]==nums[right]的处理，要令right-1

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        left = 0
        right = len(nums)-1
        while left < right:
            mid = left + ((right-left) >> 1)
            if nums[mid] < nums[right]:
                right = mid
            elif nums[mid] > nums[right]:
                left = mid+1
            else:
                right = right-1
        return nums[left]

Runtime: 56 ms, faster than 77.27% of Python3 online submissions for Find Minimum in Rotated Sorted Array II.

Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Find Minimum in Rotated Sorted Array II.

func findMin(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    left := 0
    right := len(nums) - 1
    for left < right {
        mid := (left + right) >> 1
        if nums[mid] < nums[right] {
            right = mid
        } else if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right--
        }
    }
    return nums[left]
}

Runtime: 4 ms, faster than 86.96% of Go online submissions for Find Minimum in Rotated Sorted Array II.

Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Find Minimum in Rotated Sorted Array II.

var findMin = function(nums) {
  if (nums.length === 1) {
    return nums[0]
  }
  let left = 0
  right = nums.length - 1
  while (left < right) {
    let mid = (left + right) >> 1
    if (nums[mid] < nums[right]) {
      right = mid
    } else if (nums[mid] > nums[right]) {
      left = mid + 1
    } else {
      right--
    }
  }
  return nums[left]
};

Runtime: 48 ms, faster than 95.55% of JavaScript online submissions for Find Minimum in Rotated Sorted Array II.

Memory Usage: 34 MB, less than 63.64% of JavaScript online submissions for Find Minimum in Rotated Sorted Array II.