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:
NOTE: 二分查找
- length == 1 or 2 的时候单独考虑比较稳妥，不容易出错。
- leftmost < rightmost => sorted => return leftmost
- mid+1 as one of the next boundaries
class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums)
while l < r-2:
if nums[l] < nums[r-1]:
return nums[l]
mid = (l+r)//2
if nums[mid] < nums[l]:
r = mid+1
else:
l = mid+1
if l == r-1:
return nums[l]
else:
return min(nums[l:r])
Runtime: 48 ms, faster than 73.14% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
Memory Usage: 14 MB, less than 5.40% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
Recursive solution: inspired by https://www.youtube.com/watch?v=P4r7mF1Jd50
No need to use mid+1 as boundary, since both sides are considered, and at least one side can return the result in O(1) time (at least one side is sorted).
class Solution:
def findMin(self, nums: List[int]) -> int:
def search(l,r):
if l == r-1 or nums[l] < nums[r-1]:
return nums[l]
if l == r-2:
return min(nums[l],nums[l+1])
mid = (l+r)//2
return min(search(l,mid),search(mid,r))
return search(0,len(nums))
Runtime: 52 ms, faster than 37.40% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
Memory Usage: 14 MB, less than 5.40% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
class Solution:
def findMin(self, nums: List[int]) -> int:
def search(l,r):
if l == r-1 or nums[l] < nums[r-1]:
return nums[l]
mid = (l+r)//2
return min(search(l,mid),search(mid,r))
return search(0,len(nums))
Runtime: 48 ms, faster than 73.14% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
Memory Usage: 14 MB, less than 5.40% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
