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

缺乏、安全感 2023-07-20 13:34 20阅读 0赞

![在这里插入图片描述][20200331204104596.gif_pic_center]

### 文章目录 ###

*  图解LeetCode刷题计划
 *   *  1、写在前面
     *  2、题目
     *  3、正文
     *  4、代码
     *  5、讨论

# 图解LeetCode刷题计划 #

## 1、写在前面 ##

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
今天要讲解的题目是LeetCode154题，昨天讲的，旋转的排序数组的进阶版。

[【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值（LeetCode153题）][LeetCode_LeetCode153]  
![在这里插入图片描述][20200331223510788.png]

## 2、题目 ##

首先看一下题目，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
通过改变了一个条件，就让难度从【中等】变成了【困难】。

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

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

![在这里插入图片描述][20200331223457291.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]

## 3、正文 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]  
仔细想一下就会发现，重复与否其实不影响我们的二分法，只不过在 `nums[mid] == nums[right]` 时会有影响。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]  
这里有个非常好的方法，就是 `right--`，下面简单分析一个例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]  
可以看到方法可行。  
![在这里插入图片描述][20200331223448439.png]

## 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];
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]

## 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`；

**故而没丢失。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][2020033119171520.png]

> **如果有幸帮到你，请帮我点个【赞】，给个【关注】！如果能顺带【评论】给个鼓励，我将不胜感激。**

***如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~***

***回复【数据结构】即可获取我为你准备的大礼。***

***想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~***

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]

[20200331204104596.gif_pic_center]: /images/20230528/771e94a6b46b426d8fff9bddcc51476b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/27c591a1e6e9490c8ff301686a260aac.png
[LeetCode_LeetCode153]: https://blog.csdn.net/TeFuirnever/article/details/105228617
[20200331223510788.png]: /images/20230528/3233b743e16d4acfa336ab2e79d36593.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/fdfd0a8f42eb4593b511b8064810e282.png
[20200331223457291.png]: /images/20230528/16f6e3d0f7ef490c988ce578fdae98e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/d69f1ea12dbb438394e839a33ff69914.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/12e7766e12cc4c66a286df470568e9a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]: /images/20230528/86debbab450f4477aa668d335de87dcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]: /images/20230528/59bae709c30f40b895db2042824a39fd.png
[20200331223448439.png]: /images/20230528/994718cd38204301998ce58c69b005e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]: /images/20230528/3aaf5c26c0464b3eade8f0527d4bf34d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 7]: /images/20230528/10bf4fff79b64f40a329cdf4575d8db2.png
[2020033119171520.png]: /images/20230528/5449c023cd714f9b8d9d7bcd612be331.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/8b2269f4890e453a95b1318ce8310d18.png