Floyd判圈算法——寻找重复数（C++）

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

题目思路

        这道题在LeetCode中是一道难度为中的题型，原因就是题目限制了不修改原数组并且只能用常量级的空间。

        假设没有限制，那一般的思路可以是以下几种：

        ①利用map容器，key就是nums中的数，value从0开始递增，如果value等于2时直接返回当前的nums[i]，用一次循环即可，使用的空间为O(n)；

        ②利用sort函数，对nums进行排序，由于数字都在[1, n]中并且只存在一个重复数字，用一次循环遍历，当nums[i - 1] == nums[i]时返回即可，但是修改了原数组；

        下面考虑题目限制，LeetCode官方提供了三种方法，其中一种方法利用的二进制，具体的可看官方题解，下面利用Floyd判圈算法解决这个题目。

对于Floyd算法原理可参照我的上一篇博客：Floyd判圈算法——环形链表（C++）-CSDN博客

为了方便理解，以数组：[1, 2, 3, 4, 5, 6, 4]为例：

怎么把这个数组抽象成龟兔赛跑问题呢？

抽象跑道

        从数组的第一个位置开始，nums[0]即为跑道的起点，由于nums[0] = 1， 那下一个点就是索引为1的点nums[1]；由于nums[1] = 2， 那下一个点就是nums[2]，以此类推……绘图如下： 

可以看到，我们所求的重复数就是环的入口点。 

过程推演

        最开始乌龟和兔子都在起始点1的位置，兔子的速度是乌龟的两倍，即乌龟向前走一步，兔子就向前走两步。

        第一步：寻找相遇点

        ①乌龟从1→2，兔子从1→3；

        ②乌龟从2→3，兔子从3→5；

        ③乌龟从3→4，兔子从5→4，在此刻乌龟与兔子相遇；

Notes：此时并没有结束，并不是所有的相遇点对应的值都是环的入口点，如果环上还有一个数字，相遇点就会发生改变。

        第二步：寻找环的入口点 

        将乌龟置为起点1处，将兔子置为相遇点4处，同步两者的速度为1：

        ①乌龟从1→2，兔子从4→5；

        ②乌龟从2→3，兔子从5→6；

        ③乌龟从3→4，兔子从6→4，在此刻乌龟与兔子相遇，这个时候对应的值才是正确的值，只是这个例子相遇点恰好在环的入口点上。

代码实现

class Solution {
public:int findDuplicate(vector<int>& nums) {//利用Floyd判圈算法int slow = 0;int fast = 0;do{slow = nums[slow];fast = nums[nums[fast]];}while(slow != fast);slow = 0;while(slow != fast){slow = nums[slow];fast = nums[fast];}return slow;}
};

结果展示