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