共计 426 个字符,预计需要花费 2 分钟才能阅读完成。
153. 寻找旋转排序数组中的最小值
理论在考查二分查找的办法
补充常识
double 转 int,是间接舍去小数。
负数:
向上取整 或者 向下取整 或四舍五入
Math.ceil(),Math.floor(),Math.round()
思路:
旋转后的数列会呈现以下两种状况:
- while 循环只能抉择 Left 和 Right 的起因
-
判断条件只能选 p 和 Right 的起因(红框为条件,蓝框为抉择后果)
- p>R, 只有 pR 这一种抉择;
- p<R,有这两种状况,判断后的操作都是抉择互补段Lp
- 而对于 p >L, 有两种状况,判断后的操作第一个选 pR 段,第二个选 Lp 段,无奈辨别
- p<L 只有一种 Lp 状况。
-
抉择好某一段,应该是L = p + 1,而不是 R = R – 1 的起因
- p>R,p 必然在最大值及往前,所以 L =p+1,要么 nums[p+1]= 最小值,要么在最小值往前。选 pR 段,R 不变。
- p<R,p 必然在最小值及往后,所以 R =p, 当 nums[p]= 最小值时,R=p- 1 就会跳过最小值。选 Lp 段,L 不变。
- 最终返回 p L R 都行
操作:
正文完