【手绘漫画】图解LeetCode之寻找重复数（LeetCode287题），抽屉原理
【手绘漫画】图解LeetCode之寻找重复数（LeetCode287题），抽屉原理
文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever
由于微信不允许外部链接，你需要点击页尾左下角的“阅读原文”，才能访问文中的链接。
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，但是现在出现了不等于的情况，就说明出现了重复元素，谁的元素多了，谁就有重复元素。
复杂度：
- 时间复杂度：。（二分法的时间复杂度为 ，“加上”一个
for循环，嵌套的复杂度是相乘的。） - 空间复杂度：。
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、讨论
这个题还有个神奇的解法，是快慢指针，不过不算是通解，以后会再给出的！！！
