Open Hinsverson opened 3 years ago
思路:直接二分搜索,需要总结规律参考题解 2分查找每一趟找到的mid数和r数去比,直到l=r相遇时return a[l],需要注意下面的情况,尤其是第三种:
class Solution {
func minArray(_ numbers: [Int]) -> Int {
var l = 0
var r = numbers.count - 1
while l <= r {
let mid = l + (r - l) >> 1
if numbers[mid] == numbers[r] {
r -= 1
} else if numbers[mid] > numbers[r] {
l = mid + 1
} else {
r = mid
}
}
return numbers[l]
}
}
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
示例 1:
示例 2:
注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。