写点什么

LeetCode 153. Find Minimum in Rotated Sorted Array

用户头像
隔壁小王
关注
发布于: 2020 年 05 月 07 日
LeetCode 153. Find Minimum in Rotated Sorted Array



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

Input: [3,4,5,1,2]
Output: 1



Input: [4,5,6,7,0,1,2]
Output: 0



问题分析

  1. 本题为典型的二分搜索问题;

  2. 首先根据翻转前后(Rotate/No Rotated)的不同状态,确定二分搜索的子粒度



  1. 之后,本题所求目标为数组中的最小值,因此每种状态下均始终向最小值所在的方向,逐步缩小求解区间即可。

Submission

class Solution:
def findMin(self, nums: List[int]) -> int:
n = len(nums)
left = 0
right = n - 1
while(left < right):
if(nums[left] < nums[right]):
return nums[left]
mid = left + int((right - left) / 2)
if(nums[mid] >= nums[left]):
left = mid + 1
else:
right = mid
return nums[left]



发布于: 2020 年 05 月 07 日阅读数: 38
用户头像

隔壁小王

关注

还未添加个人签名 2020.04.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 153. Find Minimum in Rotated Sorted Array