图解LeetCode刷题计划

1、写在前面

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

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

目光呆滞，今日不宜学习~

2、题目

首先看一下题目，

说到这里，就来说一下本题的关键，数字是在 1-n 之间的，只有一个重复数字！

同时有四个限制条件：

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

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

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

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

那么如何使用二分法呢？

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

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

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

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

3、正文

首先分析一下情况，

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

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

其实通过 cnt 就相当于是完成了数组的排序，把大于 mid 的放在一侧，小于等于的放在另一侧，正常情况下（没有重复元素），cnt 应该是等于 mid，但是现在出现了不等于的情况，就说明出现了重复元素，谁的元素多了，谁就有重复元素。

复杂度：

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

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

5、讨论

这个题还有个神奇的解法，是快慢指针，不过不算是通解，以后会再给出的！！！

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

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

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

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

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