【手绘漫画】图解LeetCode之寻找重复数（LeetCode287题），抽屉原理

亦凉 2023-07-21 13:28 30阅读 0赞

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

### 文章目录 ###

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

# 图解LeetCode刷题计划 #

## 1、写在前面 ##

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

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

![在这里插入图片描述][20200403225107104.png]  
目光呆滞，今日不宜学习~  
![在这里插入图片描述][20200331223510788.png]

## 2、题目 ##

首先看一下题目，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
说到这里，就来说一下本题的关键，数字是在 `1-n` 之间的，只有一个重复数字！

同时有四个限制条件：

1.  不能更改原数组（假设数组是只读的）。
2.  只能使用额外的 O(1) 的空间。
3.  时间复杂度小于 O(n2) 。
4.  数组中只有一个重复的数字，但它可能不止重复出现一次。

要注意第一个条件，所以不能排序原数组，然后再求重复的位置！！！

这里使用的方法还是二分法，不过引申出一个原理，就是——抽屉原理。

> 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。  
> ————百度百科

**那么如何使用二分法呢？**

其实也不难，思路是先拿出有效范围 `[left, right]` 里的中间数 `mid`，然后和数组中的每个元素进行比较，统计小于等于这个中间数的元素的个数 `cnt`。如果 `cnt` 大于 `mid`，依然根据抽屉原理，重复元素就应该在区间 `[left, mid]` 里，否则在区间 `[mid+1, right]`。

为啥是 `mid+1`，这个前面讲过了，自己去翻一翻吧。

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

[【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值 II（LeetCode154题）][LeetCode_ II_LeetCode154]  
![在这里插入图片描述][20200331223457291.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]

## 3、正文 ##

首先分析一下情况，

> `cnt` 代表小于等于猜测的元素的数量，`mid` 虽然是下标但是是猜测元素，这一点很重要，所以二分法的数组不再是原来的数组，而是一个新的数组了，只是没有具体的展示出来。

*  若 `cnt > mid`，说明重复数字一定在 `[left, mid]` 的范围内（因为小于等于 `mid` 的元素多，重复元素导致元素变多）；
 *  若 `cnt <= mid`，说明重复数字一定在 `(mid, right]` 的范围内（因为小于等于 `mid` 的元素少）；

其实通过 `cnt` 就相当于是完成了数组的排序，把大于 `mid` 的放在一侧，小于等于的放在另一侧，正常情况下（没有重复元素），`cnt` 应该是等于 `mid`，但是现在出现了不等于的情况，就说明出现了重复元素，谁的元素多了，谁就有重复元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]

**复杂度：**

*  时间复杂度： O ( N l o g N ) O(NlogN) O(NlogN)。（二分法的时间复杂度为  O ( l o g N ) O(logN) O(logN)，“加上”一个 `for` 循环，嵌套的复杂度是相乘的。）
 *  空间复杂度： O ( 1 ) O(1) O(1)。

![在这里插入图片描述][20200331223448439.png]

## 4、代码 ##

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

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

## 5、讨论 ##

这个题还有个神奇的解法，是快慢指针，不过不算是通解，以后会再给出的！！！  
![在这里插入图片描述][2020033119171520.png]

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

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

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

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

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

[20200403225032325.gif_pic_center]: /images/20230528/cc8c0be014ea4070b48fe3670881851f.png
[20200403225107104.png]: /images/20230528/628202dcc4034a349e703fffad522980.png
[20200331223510788.png]: /images/20230528/1c6dd65a9aa442d89d9baaa3573ed01b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/8e7e9c35e6064ddb89049794c26e480d.png
[LeetCode_LeetCode153]: https://blog.csdn.net/TeFuirnever/article/details/105228617
[LeetCode_ II_LeetCode154]: https://blog.csdn.net/TeFuirnever/article/details/105255112
[20200331223457291.png]: /images/20230528/64db5166fcbd45bb81fd34dcc29e7955.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/705d1b96873f441bbfc32fd4d5a1a95a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/7a6a73b5144e4d85962c9a7ada02659b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/54cf35018ead48fe9fab35d0ddbec102.png
[20200331223448439.png]: /images/20230528/02315281928e4ca3b1e0e3f35eb09bc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]: /images/20230528/cc55a60183334989878c7298188cf19d.png
[2020033119171520.png]: /images/20230528/9d3a39e736da4e539af96c32469be58a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/518b1886bed04e04bb529945053017a9.png