网站列表页怎么做内链,王烨乐清,石家庄百度快速排名优化,wordpress大前端d8154. 寻找旋转排序数组中的最小值 II 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java 1. 题目描述
题目中转#xff1a;154. 寻找旋转排序数组中的最小值 II
2.详细题解 该题是153. 寻找旋转排序数组中的最小值的进阶题#xff0c;在153. 寻找旋转排序数组中的最小值… 154. 寻找旋转排序数组中的最小值 II 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java 1. 题目描述
题目中转154. 寻找旋转排序数组中的最小值 II
2.详细题解 该题是153. 寻找旋转排序数组中的最小值的进阶题在153. 寻找旋转排序数组中的最小值的基础上将严格递增数组改为非递减数组即允许存在相同元素建议先尝试153. 寻找旋转排序数组中的最小值并理解后再尝试本题。 如果不考虑 O ( l o g n ) O(log n) O(logn)的时间复杂度直接 O ( n ) O(n) O(n)时间复杂度的扫描遍历一次即可。 非严格升序数组即存在相同元素的两个值。如果不旋转则最小的数值即为第一个索引为0的数值数组旋转了1到n次寻找数组中最小的元素这道题是二分查找的变型题。 对于严格递增的数组假定最小值为 m i n x min_x minx数组旋转后假定结尾最后一个值为 t a i l tail tail对于最小值 m i n x min_x minx其右边的元素均小于 t a i l tail tail而其左边的元素均大于 t a i l tail tail的值可以利用该性质使用二分查找算法。但对于非严格递增的数组来说由于存在相同值的情况因此需要单独讨论。 具体算法如下
Step1初始化两个指针 l e f t left left 和 r i g h t right right分别指向数组的起始和结束位置Step2计算中间元素的索引 m i d ( l e f t r i g h t ) / 2 mid (left right) / 2 mid(leftright)/2Step3如果 n u m s [ m i d ] n u m s [ r i g h t ] nums[mid] nums[right] nums[mid]nums[right]说明区间 ( m i d , r i g h t ] (mid, right] (mid,right]均为最小值右边的元素故移除更新 r i g h t m i d rightmid rightmid而 m i d mid mid可能为最小值因此更新区间时不能舍弃 m i d mid midStep4如果 n u m s [ m i d ] n u m s [ r i g h t ] nums[mid] nums[right] nums[mid]nums[right]说明区间 [ l e f t , m i d ] [left, mid] [left,mid]均为最小值左边的元素故移除更新 l e f t m i d 1 leftmid1 leftmid1此时 m i d mid mid值不可能为最小值因为其已经大于了结尾值故可舍弃 m i d mid midStep5否则即 n u m s [ m i d ] n u m s [ r i g h t ] nums[mid]nums[right] nums[mid]nums[right]此时难以判断是说明那个区间不包含最小值例如 [ 3 , 3 , 3 , 1 , 2 , 3 ] 、 [ 3 , 1 , 2 , 3 , 3 , 3 , 3 ] [3,3,3,1,2,3]、[3,1,2,3,3,3,3] [3,3,3,1,2,3]、[3,1,2,3,3,3,3]但由于此时它们的值均相同所以无论 n u m s [ r i g h t ] nums[right] nums[right] 是不是最小值都有一个它的「替代品」 n u m s [ m i d ] nums[mid] nums[mid]因此可以忽略二分查找区间的右端点更新 r i g h t − 1 right-1 right−1。Step6当指针left小于right时重复步骤Step2_Step6Step7否则循环结束返回 n u m s [ l e f t ] nums[left] nums[left]。
3.代码实现
3.1 Python
class Solution:def findMin(self, nums: List[int]) - int:left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] nums[right]:right midelif nums[mid] nums[right]:left mid 1else:right - 1return nums[left]3.2 Java
class Solution {public int findMin(int[] nums) {int left 0, right nums.length - 1;while (left right){int mid (left right)/2;if (nums[mid] nums[right]){rightmid;}else if (nums[mid] nums[right]){left mid 1;}else{right--;}}return nums[left];}
}执行用时不必过于纠结对比可以发现对于python和java完全相同的编写java的时间一般是优于python的至于编写的代码的执行用时击败多少对手执行用时和网络环境、当前提交代码人数等均有关系可以尝试完全相同的代码多次执行用时也不是完全相同只要确保自己代码的算法时间复杂度满足相应要求即可也可以通过点击分布图查看其它coder的code。
