leetcode-寻找旋转数组的最小值-153
2021-05-13 12:28
标签：就是 pre lse 不可 没有 上进 python 查找 二分法 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。 示例 1: 输入: [3,4,5,1,2] 输入: [4,5,6,7,0,1,2] ? 主要思想是二分查找，但是数据旋转的话不是升序或者降序，所以普通的二分法不可以，需要进化，寻找一个变化点（旋转点）：中间某一个元素大于第一个元素，那就说明变化点在右边，否则在左 leetcode-寻找旋转数组的最小值-153 标签：就是 pre lse 不可 没有 上进 python 查找 二分法 原文地址：https://www.cnblogs.com/hornets/p/13129914.html
输出: 1
示例 2:
输出: 0解题思路：
def find_min(nums):
if len(nums) == 1:
return nums[0]
left = 0
right = len(nums) -1
if nums[right] > nums[0]:
"如果最后一个元素大于第一个元素，就说明没有旋转"
return nums[0]
while right >= left:
mid = left + (right - left) // 2
"""
mid:中间值
大于下一个值就说明下一个值就是最小值
前一个值大于这个中间值，说明这个中间值就是变化点
"""
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]
if nums[mid - 1] > nums[mid]:
return nums[mid]
"""
中间值大于第一个值，说明最小值在mid右边，通过这个中间值找出变化点(旋转点)
否则在左边
"""
if nums[mid] > nums[0]:
left = mid + 1
else:
right = mid - 1
文章标题：leetcode-寻找旋转数组的最小值-153
文章链接：http://soscw.com/index.php/essay/85135.html