echo

任生命穿梭 时间的角落

0%

寻找旋转排序数组中的最小值

Posted on Edited on In Valine:

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

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

示例 2:

1
2
输入: [4,5,6,7,0,1,2]
输出: 0

使用二分查找，需要始终保持目标值在搜索范围内，并不断缩小左右边界。

我们得到的旋转数组类似于下图，为两段单调递增的序列构成，且右边序列最大值小于左边序列最小值。

image-20200722142442327

在二分查找过程中，我们有以下几种情况：

  1. 左值 < 中值，中值 < 右值，最小值在左边，[中，右]范围内的值不可能为最小值，可以收缩右边界。

    1
    2
    3
    		右
    	中
    左

  2. 左值 < 中值，中值 > 右值，最小值在右边，[左，中]范围内的值不可能为最小值，可以收缩左边界。

    1
    2
    3
    	中
    左
    		右

  3. 左值 > 中值，中值 < 右值，最小值在左边界，(中，右]范围内的值不可能为最小值，可以收缩右边界。

    1
    2
    3
    左
    		右
    	中

情况 1，3 是一类，情况 2 是另一类：

  • 如果中值 < 右值，(中，右]范围内的值不可能为最小值，可以收缩右边界。
  • 如果中值 > 右值，[左，中]范围内的值不可能为最小值，可以收缩左边界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1; //左闭右闭区间，用右开区间不方便判断右值
        while(l < r){// left == right 结束
            int mid = l + (r - l) / 2;
            if(nums[mid] > nums[r]){
                l = mid + 1; //中值 > 右值，中值不可能为最小值，左边界跳过mid
            }else if(nums[mid] < nums[r]){
                r = mid;//中值 < 右值，中值可能为最小值，右边界只能取到 mid
            }
        }
        return nums[l];
    }
}

时间复杂度O(log n)，空间复杂度O(1)。

参考：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/er-fen-cha-zhao-wei-shi-yao-zuo-you-bu-dui-cheng-z/