echo

任生命穿梭 时间的角落

0%

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

Posted on In Valine:

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

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

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

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

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

示例 2：

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

说明：

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

image-20200722142620638

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

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

    1
    2
    3
    		右
    	中
    左

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

    1
    2
    3
    	中
    左
    		右

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

    1
    2
    3
    左
    		右
    	中

  4. 中值 = 右值，最小值在左边界，右值重复(中值有可能不重复，例如 [3, 1, 1]，分别为左中右，收缩右边界变为 [3, 1])，可以收缩右边界。

    1
    2
    左
    	中   右

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

  • 如果中值 < 右值，(中，右]范围内的值不可能为最小值，可以收缩右边界。
  • 如果中值 > 右值，[左，中]范围内的值不可能为最小值，可以收缩左边界。
  • 如果中值 = 右值，右值重复，可以收缩右边界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
            }else if(nums[mid] == nums[r]){
                --r;//中值 = 右值，右值重复，右边界左移
            }
        }
        return nums[l];
    }
}

平均时间复杂度O(log n)，当数组中数字全部相等时，最坏时间复杂度O(n)。

空间复杂度O(1)。