给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的最小值为 1。
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
示例 1:
输入:numbers = [3,4,5,1,2]
输出:1
示例 2:
输入:numbers = [2,2,2,0,1]
输出:0
提示:
n == numbers.length
1 <= n <= 5000
-5000 <= numbers[i] <= 5000
numbers 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
之前写过一次这道题,当时只能按照简单题来写, 二分查找虽然看答案写出来了,但并没有真理解,只是懵懵懂懂。
这次见到重新用二分写一遍,感觉不错?
class Solution { public int minArray(int[] numbers) { int left = 0; int right = numbers.length - 1; if (numbers[left] < numbers[right]) { return numbers[left]; } while (left < right) { int mid = (left + right) / 2; // 如果右边的比中间的大,那么说明右边的部分一定是有序的。 if (numbers[right] > numbers[mid]) { right = mid; // 右边的小于中间的,说明左边的一定是有序的。 } else if (numbers[right] < numbers[mid]) { left = mid + 1; // 如果相等,想要判断哪一边是有序的比较难,需要考虑很多临界条件。 // 上次理解的难点正在这里,这次也在这里卡了思路。 // 但换个思路就很好解决了。 // 即:我不需要确认当前的状态,我只需要保证答案在我的区间内,并且逐渐压缩区间,直到出现变动即可。 // 由于此时numbers[right] == numbers[mid],所以right --并不会影响答案依旧在left和right的区间内。 } else { right --; } } return numbers[left]; } }