154. Find Minimum in Rotated Sorted Array II

Loading...LeetCode

跟 Q153 相比的不同就是可能存在重复元素了。

出现的问题就是， nums[m] == nums[r] 的情况下，转弯点可能在m 指针的右边（比如[3, 3, 1, 3] ），也可能在左边（比如[3, 1, 3, 3] ），需要单独设置一个判断来处理，直接放弃当前右端元素，重新计算m 进行比较即可，反正最小元素也不可能是右边这个（除非所有元素都相等）。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = 0, n-1
        while l < r:
            m = (l+r)//2
            if nums[m] > nums[r]:
                l = m + 1
            elif nums[m] <= nums[r]:
                r = m
            else:
                r -= 1
        return nums[l]