leetcode【困难】154、寻找旋转排序数组中的最小值 II

leetcode【困难】154、寻找旋转排序数组中的最小值 II
思路:
可以直接遍历,二分的复杂度更好一点
注意!!!可能重复!!!

class Solution {
    public int minArray(int[] numbers) {
        int l=0,r=numbers.length-1;
        while(l<r){
            int mid=(l+r)/2;
            if(numbers[r]>numbers[mid]) r=mid;
            else if(numbers[r]<numbers[mid]) l=mid+1;
            else r--;
        }
        return numbers[l];
    }
}

numbers[mid]==numbers[r]。如下图所示,由于重复元素的存在,我们并不能确定numbers[mid] 究竟在最小值的左侧还是右侧,因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是,由于它们的值相同,所以无论 numbers[r] 是不是最小值,都有一个它的「替代品」numbers[mid],因此我们可以忽略二分查找区间的右端点,直接r-1
leetcode【困难】154、寻找旋转排序数组中的最小值 II

上一篇:python测试开发django-154.bootstrap-formvalidation


下一篇:python测试开发django-154.bootstrap-formvalidation