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 rotated4
times.[0,1,2,4,5,6,7]
if it was rotated7
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]
这样做虽然是正确的,却没有通透的理解题目,利用旋转数组的旋转这一信息。数组被旋转,也就是被从被从某处截断,将前面的一段移接到后面,那么如果数组被旋转过,其右边的部分是最小值所在的区间,右边的部分要小于左边的部分。那么我们可以通过mid与right的数值比较确定mid所在的位置。如果nums[mid] < nums[right],说明mid已经在被截的这后面一部分了,有可能是最小值的位置,也可能是最小值后面的位置,right = mid, 否则如果nums[mid] > nums[right],说明mid在前面那一部分,也就是数值大的那一部分,所以l = mid+1. 直到区间缩小到 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] < nums[r]: r = mid else: l = mid+1 return nums[l]
这样才更清晰,更易懂,要明白旋转后的数组,最小值在后半段,最大值在前半段。
日期: 2021-04-11