黑龙江期刊网站制作,北京百度推广公司,微信网站制作企业,微信公众号网页文章目录 题目描述思路分析完整代码 题目描述 已知一个长度为 n 的数组#xff0c;预先按照升序排列#xff0c;经由 1 到 n 次 旋转 后#xff0c;得到输入数组。例如#xff0c;原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到#xff1a; 若旋转 4 次#xff0c;则可以… 文章目录 题目描述思路分析完整代码 题目描述 已知一个长度为 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 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 2 输入nums [2,2,2,0,1] 输出0 思路分析
寻找旋转排序数组中的最小值有俩题一个中等一个困难区别就在于数组中是否有重复数字。
先说一下中等的这个题。
题目要求 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 无疑直接二分法。
例子nums [4,5,6,7,0,1,2,3]
直接设置头尾指针left0 。right len(nums)-1。 开始二分。
这里的关键点就在于如何划分后续的left和right。
直接看一遍步骤
mid (leftright)//2 3此时mid指向数组中的7显然最小值还在右边所以当nums[mid]nums[right]时left mid1同理小于的时候 right mid这里要找的是最小值所以当大于的时候可以直接1跳过mid小于的时候由于并无法确定mid是否为最小值所以不能1跳过。
然后二分就结束了。这题就是这么简单。
再说一下这个困难题
困难题目在中等的基础上加了一个条件就是数组中可能存在相同的元素。
假设有例子 nums[4.5.6.7.0.1.1]
开始时mid指向7right指向1.显然数组向右边收缩。left 4mid5right6.此时 nums[mid] nums[right]所以right right-1.去掉重复值然后继续循环。
细节 为什么本题二分法不用 nums[m] 和 nums[i] 作比较
二分目的是判断 m 在哪个排序数组中从而缩小区间。而在 nums[m]nums[i]情况下无法判断 m 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中 i 初始值无法确定在哪个排序数组中。举例如下
对于以下两示例当 i0,j4,m2 时有 nums[m] nums[i] 而结果不同。
[1,2,3,4,5]旋转点 x0 m 在右排序数组此示例只有右排序数组。[3,4,5,1,2]旋转点 x3 m 在左排序数组。
完整代码
153题。
class Solution:def findMin(self, nums: List[int]) - int:left 0right len(nums)-1while leftright:mid (leftright)//2if nums[mid] nums[right]:left mid1else:right midreturn nums[left]154题。
class Solution:def findMin(self, nums: List[int]) - int:left 0right len(nums)-1while leftright:mid (leftright)//2if nums[mid]nums[right]:left mid1elif nums[mid]nums[right]:right midelse:right-1return nums[left]
