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
比自己实现快排要快好多……
2. Binary Search
可以用二分法:
- 左指针指向的数小于等于右指针指向的数,说明此时已经是升序的,左指针指向的数就是最小的
- 如果中间的数大于左指针的数,那么最小值在右侧,左指针等于中间位置加 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]