13518219792
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
成都网站建设哪家好，找创新互联！专注于网页设计、重庆网站建设、微信开发、小程序开发、集团成都企业网站定制等服务项目。核心团队均拥有互联网行业多年经验，服务众多知名企业客户；涵盖的客户类型包括：花箱等众多领域，积累了大量丰富的经验，同时也获得了客户的一致赞美！
class Solution:
"""
由于整个数组在一定程度上是有序的，因此可以借鉴二分查找的思想，达到接近O(logn)的时间复杂度。
将一个有序(升序)数组的前x个元素挪到末尾，这里可以分类进行讨论。
第一类：挪动元素个数为数组长度的整数倍，那么这时候等于没有挪动，最小值出现在idx=0
第二类：挪动元素个数不是数组长度的整数倍，那么这时候挪动后的数组可以分成两个子数组，其中左边子
数组的元素都是大于等于右边子数组的。
[3, 4, 5, 1, 2]
这时候我们维护两个指针p1和p2，分别指向左边子数组和右边子数组。当中间元素大于等于p1指向
的元素的时候，则中间元素属于左边子数组，反之属于右边子数组。
当两个指针相邻的时候p2就指向了右边子数组的第一个元素，也就是整个数组的最小值。
第三类：[1, 0, 1, 1, 1]
当p1和p2指向的元素和中间的元素相等的时候，这时候如果按照第二类的思路，那么会误判最小值
在中间元素之后，因此这种情况下我们需要顺序查找。
"""
def minNumberInRotateArray(self, rotateArray):
if not rotateArray:
return 0
# 将mid初始化为0，可以处理第一类情况，因为这时不会进入循环，直接输出最小值
left, mid, right = 0, 0, len(rotateArray) - 1
while rotateArray[left] >= rotateArray[right]:
# 如果left和right已经相邻，那么最小值就是right指向的元素
if left == right - 1:
mid = right
break
mid = (left + right) >> 1
# 如果left, right, mid指向的元素都相等，那么需要对这个区间进行顺序查找，否则按照
# 第二类情况的解题思路会判断错误
if rotateArray[left] == rotateArray[mid] == rotateArray[right]:
return min(rotateArray[left:right + 1])
# 中间元素在左半边，最小值出现在右边子数组[mid, right]
if rotateArray[left] <= rotateArray[mid]:
left = mid
# 中间元素在右半边，最小值出现在左边子数组[left, mid]
else:
right = mid
return rotateArray[mid]
