11. 旋转数组的最小数字
文章目录
11. 旋转数组的最小数字
本题是这道题153. 寻找旋转排序数组中的最小值的延伸,建议先看这道题。

思路:
本题中的数组元素可以重复,那么除了nums[p]>nums[R] nums[p]<nums[R]的情况,还多出一种情况:nums[p] = nums[r],如图。
1、此时不知道最小值在p的左边还是右边,无法断定取Lp段还是pR段。
2、而知道nums[R]是重复的,可以舍去一个。
3、因此,R--,向里移动一个,这样既不会漏掉最小,还缩小了范围。
4、同时还会更新p,如果还相等就再来亿次。比如第二个图,就是缩了两次才找到不等的nums[p]>nums[R]。

操作:

有大佬的解析说明了当存在nums[p] = nums[R]的情况时,j--,其实跟直接遍历差不多了。
操作:

若想将循环改为闭环:left<=right,最后取right值就好。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论