Floyd快慢指针算法

好久没在 leetcode 上刷题了，近几日心血来潮，搞了起来，发现有些生疏了。

题目

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

题解

看了题解，发现竟然真有O(n)的做法，竟然不该变原数组！Amazing! 原来是使用了快慢指针算法，leetcode 上给出了非常详细的讲解，建议去看看那个链接。

这题和环形链表有什么关系呢？由于题目的特殊性，nums[i] >= 1 && nums[i]<=n。所以可以这样转换，对于nums中每一个位置 i 和 nums[i] 之间连接一条有向边，从前者指向后者，这样可以构成一张图，其中图的节点为0-n的数值。

举例：比如 nums[] = {1,4,6,6,6,2,3};

0 ->1表示 0 -> nums[0] , 1 -> 4 表示 1 -> nums[1]， 以此类推得到下图：

graph LR
0 --> 1
1 --> 4
4 --> 6
2 --> 6
3 --> 6
5 --> 2
6 --> 3

可以看到图中构成了环，其中入口节点 6 即为重复元素

那么因为有重复元素，那么必定存在某个节点，有两个不同的边指向它，所以图会构成环。 而环的入口即为寻找的重复元素，所以可以使用快慢指针算法来求解。

实现代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        //寻找相聚点
        while(slow != fast || slow == 0){
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        }
        //寻找入口节点
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }
};