LeetCode-中等-287-寻找重复数【Floyd 判圈算法】

本文主要记录《LeetCode-中等-287-寻找重复数》这一题目的解法。

涉及【Floyd 判圈算法】，又称【弗洛伊德的乌龟和兔子】，本质是【快慢指针】。

题目

题目链接点击此处

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1：

输入: [1,3,4,2,2]
输出: 2

示例 2：

输入: [3,1,3,4,2]
输出: 3

说明：

1. 不能更改原数组（假设数组是只读的）。
2. 只能使用额外的 O(1) 的空间。
3. 时间复杂度小于 O(n^2)。
4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

解法

题目说明中有许多限制，如果不看限制的话，还可以有两种解法，此处只提一下，不对这两种解法做讲解。

1. 排序：
   1. 排序后遍历数组，因为存在重复的元素，所以一定有相邻的元素相等，找到相等的元素即可。
   2. 时间复杂度 O(nlogn)，空间复杂度 O(1)。
2. 使用 Set 数据结构：
   1. 遍历数组，判断 Set 中是否存在当前元素，不存在则将该元素加入 Set 中，存在则说明该元素就是重复的数字。
   2. 时间复杂度 O(n)，空间复杂度 O(n)。

Floyd 判圈算法

首先，我们可以将数组看作是一个链表，元素的值可以看作是指向下一个元素的索引。

比如示例 1 中，nums[0] = 1，所以下一个访问的元素下标为 1，nums[1] = 3，所以再下一个访问的元素下标为 3，以此类推。

于是我们设置两个指针，一个指针一次走一步，另一个指针一次走两步。

因为数组中存在重复的数字，所以会访问到同一个下标，导致产生环，环的入口就是重复的数字。

因此，一直访问下去，指针最终会处于循环内，即快慢指针最终会在循环内相遇。

int tortoise = 0; // 慢指针
tortoise = nums[tortoise]; // 一次走一步
int hare = 0; // 快指针
hare = nums[nums[hare]]; // 一次走两步

假设从起点到环的入口一共是 m 步，环的周长是 c 步。

相遇时 tortoise（慢指针）一共走了 n 步，那么 hare（快指针）则走了 2n 步。

因为此时 tortoise 和 hare 在环中的同一点，所以 hare 多走的 n 步相当于快了 tortoise 一或多圈。

所以 n 是 c 的倍数，即 n % c = 0。

而 tortoise 在循环内走的步数为 n - m，如果让 tortoise 再走 m 步，那么 tortoise 一定会回到环的起点。

于是，此时再设置一个 finder 指针，从 0 开始，让 tortoise 和 finder 同步前进。

那么 m 步后，finder 和 tortoise 会在环的入口处相遇，而环的入口就是重复的数字。

代码实现（C# 语言描述）

public int FindDuplicate(int[] nums)
{
    int tortoise = nums[0];
    int hare = nums[nums[0]];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
    }
    int finder = 0;
    while (tortoise != finder) {
        tortoise = nums[tortoise];
        finder = nums[finder];
    }
    return finder;
}