旋转数组的最小数字第三次

剑指 Offer 11. 旋转数组的最小数字

难度简单294

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

通过次数176,968

提交次数359,125

第N次做

class Solution {
    public int minArray(int[] nums) {
        int l=0,r=nums.length-1,mid = 0;
        while(l<=r){
            mid = l+(r-l)/2;
            // 这里有可能mid就是最小值，所以不能 mid - 1
            if(nums[mid] < nums[r]){
                // mid在右边升序部分
                r = mid;
            }else if(nums[mid] > nums[r]){
                // mid在左边升序部分
                l = mid + 1;
            }else{
                r--;
            }
        }
        return nums[mid];
    }
}

官方题解二分查找

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

class Solution{
    public static int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1, mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if (numbers[left] < numbers[mid] && numbers[mid] > numbers[right]) {//左边递增，并且中间值大于右边的值
                left = mid;//左指针右移
            } else if (numbers[left] > numbers[mid] && numbers[mid] < numbers[right]) {//在右半边递增部分
                right = mid;//右指针左移
            } else {
                return getMIn(numbers, left, right);
            }
        }
        return numbers[left];
    }
    //顺序查找
    public static int getMIn(int[] number, int start, int end) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < number.length; i++) {
            min = Math.min(min, number[i]);
        }
        return min;
    }
}

清晰题解

class Solution {
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int m = (l + r) / 2;
            // 如果中间的大于右边，说明更小的值在右边
            if (numbers[m] > numbers[r]) l = m + 1;
            // 如果中间的小于右边，说明更小的值可能在中间或者中间往左边的部分
            else if (numbers[m] < numbers[r]) r = m;
            // 否则数字是相同的，不是递增或者递减的，右边界收缩
            else r--;
        }
        return numbers[l];
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信