1.可以修改数组，找出重复的数字
基于交换的思想O ( N ) O(N)O(N)+O ( 1 ) O(1)O(1)
classSolution{public:intduplicateInArray(vector<int>&nums){intn=nums.size();for(inti=0;i<n;i++){if(nums[i]<0||nums[i]>=n)return-1;}for(inti=0;i<n;i++){while(nums[i]!=i&&nums[i]!=nums[nums[i]]){swap(nums[i],nums[nums[i]]);}}for(inti=0;i<n;i++){if(nums[i]!=i)returnnums[i];}return-1;}};2. 不修改数组，找出重复的数字，O(1) 空间
抽屉原理 + 二分答案O ( N l o g N ) O(NlogN)O(NlogN)
抽屉原理：n + 1 n+1n+1个苹果放在n nn个抽屉里，那么至少有一个抽屉中会放两个苹果。
用在这个题目中就是，一共有n + 1 n+1n+1个数，每个数的取值范围是1 11到n nn，所以至少会有一个数出现两次。
然后我们采用分治的思想，将每个数的取值的区间[ 1 , n ] [1, n][1,n]划分成[ 1 , n / 2 ] [1, n/2][1,n/2]和[ n / 2 + 1 , n ] [n/2+1, n][n/2+1,n]两个子区间，然后分别统计两个区间中数的个数。注意这里的区间是指数的取值范围，而不是数组下标。
划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于n nn，和有n + 1 n+1n+1个数矛盾。
因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了两次。
依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1 11时，我们就找到了答案。
classSolution{public:intduplicateInArray(vector<int>&nums){intl=1,r=nums.size()-1;while(l<r){intmid=l+r>>1;intcnt=0;// [l, mid], [mid + 1]for(intx:nums){if(x>=l&&x<=mid)++cnt;}if(cnt>mid-l+1)r=mid;elsel=mid+1;}returnl;}};模拟链表（转换为求环的入口节点问题）O ( N ) O(N)O(N)
1. 核心思路
给定一个长度为 (n+1) 的数组nums，其中所有元素的取值范围均为 ([1,n])。
我们可以将数组转换成一个有向图，具体映射关系如下：
- 数组下标
i表示节点的编号。 - 数组元素
nums[i]表示节点i指向的下一个节点。 - 因此，每个节点都存在一条有向边
i → nums[i]。
由于数组长度为 (n+1)，所以节点编号范围为 ([0,n])，但数组元素的取值范围只有 ([1,n])。
这意味着：
- 图中共有 (n+1) 个节点。
- 每个节点都恰好有一条出边。
- 所有节点的出边都只能指向节点 (1\sim n)。
- 节点 0 不可能被其他节点指向，因此节点 0 的入度为 0。
我们可以利用这一特殊性质，从节点 0 出发，通过 Floyd 快慢指针算法寻找环的入口，从而得到一个重复数字。
2. 为什么从节点 0 出发一定会进入环？
从节点 0 开始，不断根据数组元素寻找下一个节点：
[ 0\rightarrow nums[0]\rightarrow nums[nums[0]]\rightarrow\cdots ]
由于所有节点都恰好有一个后继节点，因此可以不断沿着指针向后访问。
但图中只有有限的 (n+1) 个节点，根据抽屉原理，在不断访问的过程中，必然会再次访问某个已经访问过的节点。
一旦出现重复访问，就说明路径中形成了一个环。
因此，从节点 0 出发，一定能够进入某个环。
3. 为什么环的入口一定是重复数字？
这是整个算法正确性证明中最重要的部分。
假设从节点 0 出发，经过若干节点后第一次进入环，环的入口节点为 (k)。
我们已经知道，节点 0 的入度为 0，因此节点 0 不可能属于任何环。
所以，从节点 0 到环的入口之间，必然存在一段非环形路径。
此时，环的入口节点 (k) 必然存在两条来自不同节点的入边：
- 一条来自环外路径上的最后一个节点，假设为 (i)。
- 另一条来自环内的前一个节点，假设为 (j)。
因此：
n u m s [ i ] = n u m s [ j ] = k , i ≠ j nums[i]=nums[j]=k,\qquad i\ne jnums[i]=nums[j]=k,i=j
这意味着数组中至少存在两个不同位置，其元素值均为 (k)。
所以：
环的入口节点 k 对应一个重复数字 \text{环的入口节点 }k\text{ 对应一个重复数字}环的入口节点k对应一个重复数字
至此，我们就完成了问题的转化：
寻找数组中的重复数字，可以转化为从节点 0 出发，寻找有向图中的环入口。
四、举例说明
给定：
nums = [2, 3, 5, 4, 3, 2, 6, 7]从节点 0 出发：
0 → 2 → 5 → 2 → 5 → ...可以发现：
- 节点 0 是起点，不在环中。
- 节点 2 是环的入口。
- 节点 0 和节点 5 都指向节点 2。
即：
nums[0] = 2; nums[5] = 2;因此，重复数字为 2。
注意，这个例子中数字 3 也重复了，但算法只要求找到任意一个重复数字，因此返回 2 完全正确。
五、使用 Floyd 快慢指针寻找环入口
证明数组可以转换为带环的链表后，就可以使用 Floyd 判圈算法。
算法分为两个阶段。
第一阶段：寻找快慢指针的相遇点
intfast=0,slow=0;do{fast=nums[nums[fast]];slow=nums[slow];}while(fast!=slow);快指针每次移动两步，慢指针每次移动一步。
由于从节点 0 出发必然进入环，快慢指针最终一定会在环内相遇。
但要注意：第一次相遇的位置不一定是环的入口。
第二阶段：寻找环的入口
intidx1=0,idx2=fast;while(idx1!=idx2){idx1=nums[idx1];idx2=nums[idx2];}returnidx1;将一个指针放回起点 0，另一个指针保留在第一次相遇的位置。
随后两个指针都以每次一步的速度移动，最终会在环的入口相遇。
此时返回的节点编号，就是数组中的一个重复数字。
6. 代码
classSolution{public:intduplicateInArray(vector<int>&nums){intfast=0,slow=0;// 第一步：寻找快慢指针相遇点do{fast=nums[nums[fast]];slow=nums[slow];}while(fast!=slow);// 第二步：寻找环的入口intidx1=0,idx2=fast;while(idx1!=idx2){idx1=nums[idx1];idx2=nums[idx2];}returnidx1;}};
