网站顶部悬浮广告代码,网站统计数据分析,怎么做微信网站吗,做搜狗pc网站快速题目#xff1a;
已知一个长度为n的数组#xff0c;预先按照升序排列#xff0c;经由1到n次旋转后#xff0c;得到输入数组#xff0c;例如#xff0c;原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到#xff1a;
若旋转 4 次#xff0c;则可以得到 [4,5,6,7,0,1,2]若…题目
已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
给定一个元素互不相同的数组nums,它原来是一个升序排列的数组并按上述情形进行了多次旋转找出并返回数组中的最小元素。 题目二分查找
一个不包含重复元素的升序数组在经过旋转之后可以得到下面可视化的折线图 其中横轴表示数组元素的下标纵轴表示数组元素的值。图中标出了最小值的位置是我们需要查找的目标。
考虑数组中的最后一个元素x:在最小值右侧的元素不包括最后一个元素本身,它们的值一定都严格小于 x而在最小值左侧的元素它们的值一定都严格大于 x。因此可以通过二分查找的方法找出最小值。
在二分查找的每一步中左边界为 low右边界为 high区间的中点为 pivot最小值就在该区间内。将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较
可能会有以下的三种情况
第一种情况是 nums[pivot]nums[high]。如下图所示这说明 nums[pivot] 是最小值右侧的元素因此我们可以忽略二分查找区间的右半部分。 第二种情况是 nums[pivot]nums[high]。如下图所示这说明 nums[pivot] 是最小值左侧的元素因此我们可以忽略二分查找区间的左半部分。 由于数组不包含重复元素并且只要当前的区间长度不为 1pivot 就不会与 high 重合而如果当前的区间长度为 1这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]nums[high] 的情况。
当二分查找结束时就得到了最小值所在的位置。
class Solution(object):def findMin(self, nums)::type nums: List[int]:rtype: intlow,high0,len(nums)-1 #初始化两个指针low和high分别指向数组的开始(0)和结束位置while lowhigh:#当low指针小于high指针时继续循环midlow(high-low)//2 #计算中间位置if nums[mid]nums[high]: #说明最小值在左半部分highmid #将右指针移动到中间位置else: #说明最小值在右半部分lowmid1return nums[low] #low high指向的就是最小值的位置
时间复杂度为 O(logn)其中 n 是数组 nums 的长度
空间复杂度O(1)
源自力扣官方题解
