LeetCode 287. 寻找重复数
题目
\287. 寻找重复数
中等
2.1K
相关企业
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
思路1 双指针找环
类似于在单链表中寻找环的思路。
参考https://leetcode.cn/problems/find-the-duplicate-number/solutions/58841/287xun-zhao-zhong-fu-shu-by-kirsche/链接中的：
主要讲解为什么没有重复的数字就不会产生环
主要思路是反证
产生环就是下标不停地循环，那么等价于：至少有两个位置可以达到某一个点，比如上面图中的2,3和4都可以到2这个节点。即至少有两个节点都保存相同的数字，这与没有重复数字是矛盾的。因此没有重复数字就不会产生环。
同理也可以推断出有重复数字就一定可以产生环。
那么本题就变成了，如何找到环的入口。
思路参考
环形链表II
环形链表那道题有两种思路，一种是记录重复数字，一种就是记录快慢双指针（这两个思路在随想录中都有详细讲解，这里就不再赘述了。）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0;int fast = 0;
int n = nums.size();
while(true){
// 肯定有环
fast = nums[nums[fast]];
slow = nums[slow];
if(fast == slow){
break;
}
}
//现在fast和slow都指z和y的交接点
int newSlow = 0;
while(true){
if(nums[newSlow] == nums[slow]){
return nums[slow];
}else{
newSlow = nums[newSlow];
slow = nums[slow];
}
}
return 0;
}
};
参考本题题解和代码随想录中有一篇讲解寻找单链表中的环的题解
思路2 二分查找重复数字
这个的时间复杂度应该是O（nlogn），稍微超了一点，但是没有用到多余的空间。
本思路精妙在于二分法中的
left，mid，right不再是下标，而是具体的数字。
在这个本题不能修改数组的情况下下如何二分来解决问题呢？直接上关键伪代码。
一定要牢记本题中的
left、right和mid不是下标，而是对应的数字
while(left < right){
//任意一个数字都行，但是为何最快，肯定是用中间的那个数字
int mid = 数组中的一个数字
int count = 数组中小于等于mid的数字的数量
if(count >不重复数组中该有的值){
//说明本数组中小的数字太多了（重复了），说明区间应该左移
right 变小;
}else{
//反之说明大的数字多了
left 变大;
}
}
return nums[right];
全部代码：
class Solution {
public:
int getCount(int mid,vector<int>& nums){
int res = 0;
for(auto item:nums){
if(item <= mid){
res++;
}
}
return res;
}
int findDuplicate(vector<int>& nums) {
int left = 1;int right = nums.size() -1 ;
while(left < right){
int mid = (left + right)>> 1;
int count = getCount(mid,nums);
int correctCount = mid ;//如果不重复，那么[1,n]中 小于等于mid的数量就是mid
cout<<"left: "<<left<<" right:"<<right;
cout<<" mid:"<<mid<<" count:"<<count<<" correctCount:"<<correctCount<<endl;
if(count > correctCount){
//小的数太多了
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
};