【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值 II（LeetCode154题）

1、前言

手绘漫画系列正式上线！！！"图解LeetCode刷题计划" 来了！！！

今天是第二期，争取每天一期，最多两天一期，欢迎大家监督我。。。公众号监督最好！！！

今天要讲解的题目是LeetCode154题，昨天讲的，旋转的排序数组的进阶版。

【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值（LeetCode153题）

2、题目

首先看一下题目，

通过改变了一个条件，就让难度从【中等】变成了【困难】。

新增的条件是元素可以重复。

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

3、正文

首先分析一下情况，和昨天的题相比，差别就在于数组元素是否有重复。

仔细想一下就会发现，重复与否其实不影响我们的二分法，只不过在 nums[mid] == nums[right] 时会有影响。

这里有个非常好的方法，就是 right--，下面简单分析一个例子：

可以看到方法可行。

4、代码

int findMin(int* nums, int numsSize){
    int left=0;int right=numsSize-1;
    while(right>left){
        int mid=left+(right-left)/2;
        if(nums[mid]>nums[right]){
            left=mid+1;
        }
        else if(nums[mid]<nums[right]){
            right=mid;
        }
        else{
            right--;
        }
    }
    return nums[left];
}

5、讨论

下面提一个问题，在执行 right-- 时，最小值是否会有丢失？

假设 nums[right] 是最小值，有两种情况：

• nums[right] 一定不可能是唯一最小值，不然就无法满足判断条件 nums[mid] == nums[right] 了；
• 若 nums[right] 不是唯一最小值，即存在多个相同的最小值，由于 mid < right （昨天证明了）而 nums[mid] == nums[right]，一定还有最小值存在于 [left, right - 1] 区间：
  • 或者存在 mid 及 mid 的右侧；
  • 或者存在 left 及 mid 的左侧，还有 right；

故而没丢失。