153. 寻找旋转排序数组中的最小值 [medium]

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

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

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

通过次数56,830 | 提交次数111,352

First Try

2020-07-03

提供一个额外变量标记最小值，画个图切割下，结合前面的几道旋转题目就很简单了。

不过看题解，并不需要使用额外标记，直接一路往前怼，知道想要的在哪个方向。还是使用额外标记好，一些琐碎的边界问题不用考虑得那么清楚。只要复杂度在同一个等级就行，并不在乎是否优化到了极限。

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 依然是每次对半切分
        if not len(nums):
            return None
        minv = nums[0]
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            minv = min(minv, nums[mid])
            # 左侧有序
            if nums[left] < nums[mid] or nums[mid] > nums[right]:
                minv = min(minv, nums[left])
                left = mid + 1 # 跳到右侧去
            elif nums[mid] < nums[right] or nums[mid] < nums[right]:
                minv = min(minv, nums[mid])  # 其实不需要判断了
                right = mid - 1 # 跳到左侧去
            else:  # 如果不存在相等的话，不需要这一步
                left += 1
                right -= 1
        return minv

153. 寻找旋转排序数组中的最小值 [medium]​

First Try​

153. 寻找旋转排序数组中的最小值 [medium]

First Try