【剑指offer】11 旋转数组的最小数字
2021-01-22 13:17
标签：lse 大于 排序 else 数值 style == describe ack 1.从题目看就是一个有序数组分成AB，旋转后变为BA，找出A的第一个数值。for循环O(n)可以直接查，或者直接返回min 2.数组的查找优先使用二分法查找，定义mid， mid若是大于high，则说明min现在在B里，low往右变为mid+1，至少是mid加一，因为现在mid还在B里； mid若是小于high，则说明mid现在就在A里了，high往左移变为mid，不用减一，万一就是min了呢 mid若是等于high，无法判断mid在哪里，（3 2 2 2）但因为是非递减排序，执行high-- 不断缩小范围后，low为现在最小的元素 1. 2. 【剑指offer】11 旋转数组的最小数字 标签：lse 大于 排序 else 数值 style == describe ack 原文地址：https://www.cnblogs.com/fuj905/p/12888476.html题目描述
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。分析
解题
class Solution:
def minArray(self, numbers: List[int]) -> int:
if len(numbers) == 0:
return 0
# return min(numbers)
for i in range(len(numbers)-1):
if(numbers[i]>numbers[i+1]):
return numbers[i+1]
return numbers[0]
class Solution:
def minArray(self, numbers: List[int]) -> int:
if len(numbers) == 0:
return 0
i, j = 0, len(numbers) - 1
while i j:
m = (i + j) // 2
if numbers[m] > numbers[j]:
i = m + 1
elif numbers[m] numbers[j]:
j = m
else:
j -= 1
return numbers[i]
文章标题：【剑指offer】11 旋转数组的最小数字
文章链接：http://soscw.com/index.php/essay/45449.html