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.

You may assume no duplicate exists in the array.

Example 1:

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

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

Solutions

　　注意这里是没有重复数值的，如果有重复数值就会有问题，需要看 154 题看有重复的解法。

1. Sort

　　直接排序也可以，但是比较慢。

class Solution(object):
    def partition(self, nums, low, high):
        i = low
        pivot = nums[high]
        for j in range(low, high):
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[high] = nums[high], nums[i]
        return i
    
    def quick_sort(self, nums, low=0, high=None):
        if not high:
            high = len(nums) - 1
        def _quick_sort(nums, low, high):
            if low >= high:
                return
            piovt = self.partition(nums, low, high)
            _quick_sort(nums, low, piovt-1)
            _quick_sort(nums, piovt+1, high)
        
        _quick_sort(nums, low, high)
        return nums
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.quick_sort(nums)[0]
# Runtime: 24 ms, faster than 90.52% of Python online submissions for Find Minimum in Rotated Sorted Array.
# Memory Usage: 12.1 MB, less than 9.23% of Python online submissions for Find Minimum in Rotated Sorted Array.

# Runtime: 916 ms, faster than 11.36% of Python online submissions for Find Minimum in Rotated Sorted Array.
# Memory Usage: 15.4 MB, less than 5.18% of Python online submissions for Find Minimum in Rotated Sorted Array.

　　发现直接用 sorted 比自己实现快排要快好多……

　　可以用二分法：

  1. 左指针指向的数小于等于右指针指向的数，说明此时已经是升序的，左指针指向的数就是最小的
  2. 如果中间的数大于左指针的数，那么最小值在右侧，左指针等于中间位置加 1
  3. 如果中间数小于左指针的书，那么最小值在左侧，右指针等于中间值位置
    1. 有可能中间数自己就是最小值，所以这里不能在右指针基础上减 1
# Time: O(logn)
# Space: 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[r]:
                l = mid + 1
            else:
                r = mid
# 146/146 cases passed (40 ms)
# Your runtime beats 91.62 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)

　　当然也可以跟 154 一样，用 mid 跟 left 对比：

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]

References

  1. 153. Find Minimum in Rotated Sorted Array
  2. huahua