力扣287-寻找重复数

287. 寻找重复数 - 力扣（LeetCode）

给定一个包含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

示例 3 :

输入：nums =[3,3,3,3,3]
输出：3

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums中只有一个整数出现两次或多次，其余整数均只出现一次

进阶：

• 如何证明nums中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度O(n)的解决方案吗？

对 i=0,1,2,…,n，连一条从 i 到nums[i]的有向边，得到一个有向图

每个节点的入度，都表示这个节点在 nums 中的出现次数

以示例一的[1, 3, 4, 2, 2]为例

因为2出现了两次，下标分别为3和4，所以一定会有 3 -> 2 和 4 -> 2 两条边，2 的入度就是它出现的次数

严谨地说，假设nums[i] == nums[j] == k，即 k 为那个重复出现的数，那么就必然建立 i -> k 和 j -> k 两条边

由于每个节点的出度都为1（因为下标唯一），所以 n + 1 个节点有 n + 1 条边，这样的有向图必然有环，找到环的入口即可

注意，可能有多个连通块，例如[1, 2, 1, 4, 3]中，3 和 4 是互相指向的，两个节点构成一个连通块。因此要从节点 0 出发寻找

那么问题就变成了找链表中环开始的节点，使用 Floyd 判圈算法，其实就是快慢指针

假设头节点到入环口要走 a 步，环长为 b，相遇时慢指针走了 c 步，那么快指针走了 2c 步，设快指针比慢指针多走了 k 圈，则有：2c - c = kb，即 c = kb

慢指针从入环口开始，在环中走了 c - a = kb - a 步到达相遇点

对于快指针，从入环口开始，在环中走了 2kb - a 步到达相遇点

那么如果同时让快慢指针再走 a 步，慢指针从入环口开始在环中走了 kb 步，快指针则是 2kb 步，而环长为 b，所以此时慢指针从入环口开始走了 k 圈，快指针 2k 圈，刚好为整数，意味着相遇点再走 a 步，就是入环口

也就是说，相遇后，我们可以让一个新指针从头节点出发，让慢指针从相遇点出发，二者相遇的点就是入环口。因为慢指针差 a 步到相遇点，而 a 的含义就是头节点到入环口的步数

class Solution { public int findDuplicate(int[] nums) { int slow = 0, fast = 0; // 0必定不在环上，因为入度为0 while(true) { slow = nums[slow]; // slow = slow.next fast = nums[nums[fast]]; // fast = fast.next.next if(fast == slow) { break; } } int head = 0; while(slow != head) { slow = nums[slow]; head = nums[head]; } return slow; } }