首页 > 其他 > 详细

Leetcode 153. Find Minimum in Rotated Sorted Array

时间:2021-04-11 21:14:29      阅读:14      评论:0      收藏:0      [点我收藏+]

Description: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Link: 153. Find Minimum in Rotated Sorted Array

Examples:

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

思路: 找到被旋转的数组中的最小值,给定的target值有确定的值,可以直接找,那么最少值呢?它在这个数组中有什么特点,可以作为一个标准找到呢?如果一个数的前面的值大于它,它就是最小的,如果一个值后面的值小于它,那么它后面的值就是最小值。其他情况就是有序的情况,移动指针就可以。注意为了使mid+1不越界,设置 while l < r,不是以前的 while l <= r。

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

日期: 2021-04-11 

Leetcode 153. Find Minimum in Rotated Sorted Array

原文:https://www.cnblogs.com/wangyuxia/p/14644294.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!