【4.9】LeetCode每日一题· 寻找旋转排序数组中的最小值 II

2021年04月09日 11时15分

标签： LeetCode 二分

## 题目描述
已知一个长度为`n`的数组，预先按照升序排列，经由`1`到`n`次**旋转**后，得到输入数组。例如，原数组`nums = [0,1,4,4,5,6,7]`在变化后可能得到：
* 若旋转`4`次，则可以得到`[4,5,6,7,0,1,4]`
* 若旋转`7`次，则可以得到`[0,1,4,4,5,6,7]`

注意，数组`[a[0], a[1], a[2], ..., a[n-1]]`**旋转一次**的结果为数组`[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`。

给你一个可能存在**重复**元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

#### 示例1
```
输入：nums = [1,3,5]
输出：1
```

#### 示例2
```
输入：nums = [2,2,2,0,1]
输出：0
```

#### 提示
```
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
```

### 进阶
* 这是[搜索旋转排序数组](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/)的延伸题目，本题中的`nums`可能包含重复元素。
* 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/ "题目链接")

## 解题思路
和前天[搜索旋转排序数组II](http://www.vison307.com/59/)两题思路类似。

此外，注意到旋转升序数组的一个重要性质：**如果将其头尾相连，那么存在且仅存在一处位置，有前一个位置的值大于后一个位置的值。**

由于数组中包含重复元素，因此可能无法判断下一次二分应该取哪一个区间，因此需要对端点进行遍历。

在数组中所有元素相等时，达到最坏情况下的时间复杂度$$O(n)$$，对于一个随机的数组，平均时间复杂度$$O(\\log n)$$。

具体解释详见代码。

此外[官方题解](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui--16/)的写法更简洁，常数更低。在此记录一下。

## 代码
```cpp
class Solution {
public:
    int findMin(vector<int>& nums) {
        // 旋转升序数组有一个性质：如果将其头尾相连，那么存在且仅存在一处位置，有前一个位置的值大于后一个位置的值
        int l = 0, r = nums.size()-1, mid, res = nums[0];
        while(l < r){
            mid = (r - l) / 2 + l;
            if(nums[l] == nums[mid] && nums[mid+1] == nums[r]){
                // 四个端点全部相等，无法判断下一次应该二分哪个区间
                if(nums[mid] == nums[mid+1]){
                    r--;
                }else{
                    // 可以断定该子数组的最小值在左边, 且为nums[l]
                    if(nums[l] < nums[r]){
                        return min(res, nums[l]);
                    // 可以断定该子数组的最小值在右边, 且为nums[r]
                    }else{
                        return min(res, nums[r]);
                    }
                }
            }else{
                // 可以断定左边是非递减的，那么最小值要么是nums[l], 要么在右边。继续二分
                if(nums[l] <= nums[mid]){
                    res = min(res, nums[l]);
                    l = mid+1;
                //可以断定右边是非递减的，且左边不是非递减的，因此最小值一定在左边。继续二分
                }else{
                    r = mid;
                }
            }
        }
        return min(res, nums[l]);
    }
};
```

## 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了60.56%的用户
> 内存消耗：12 MB，在所有 C++提交中击败了25.14%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.9】LeetCode每日一题· 寻找旋转排序数组中的最小值 II

所有评论

暂无评论

新增评论