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–,其实跟间接遍历差不多了。
操作: