Description

Suppose an array sorted in ascending order 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.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

Solutions

  154 题相对于 153 题是考虑了重复的情况,相对来说复杂一些了!需要考虑类似 2222122 的情况。

  如果有重复的话,需要跟左边的数进行比较,注意顺序。

  1. 左指针的书小于(不含等于)右指针的话,那么最小值就是左指针的数
  2. 如果左指针数等于中间的数,那么左指针就加 1
    1. 这里更新左指针不是在 mid 基础上加 1,是因为可能出现 2222122 的情况
  3. 如果左指针数大于中间的数,右指针更新为 mid
  4. 如果左指针数小于中间的数,左指针更新为 mid+1
# O(logn)
# O(1)
class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            if nums[l] < nums[r]:
                return nums[l]
            mid = (l + r) >> 1
            if nums[mid] == nums[l]:
                l += 1
            elif nums[mid] > nums[l]:
                l = mid + 1
            else:
                r = mid
        return nums[l]
# 192/192 cases passed (48 ms)
# Your runtime beats 97.99 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.1 MB)

References

  1. 154. Find Minimum in Rotated Sorted Array II