每日题解: LeetCode 287. 寻找重复数

题目地址

题目描述

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

示例 1:

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

输入: [3,1,3,4,2]
输出: 3
说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。

解法

class Solution {
    public int findDuplicate(int[] nums) {
 int slow = 0, 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;
    }
}

解题思路

Floyd 判圈算法

1.分析题目要求

只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。

限制了我们不能使用map,set等数据接口，也不能循环嵌套
2.关于Floyd 判圈算法

Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm),是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。

首先假设第一次相遇的时候慢指针走过的节点个数为i，设链表头部到环的起点的长度为m，环的长度为L，相遇的位置与起点与起点位置距离为k。
于是有：
i = m + a * L + k
其中a为慢指针走的圈数。

因为快指针的速度是慢指针的2倍，于是又可以得到另一个式子：
2 * i = m + b * L + k
其中b为快指针走的圈数。

两式相减得：
i = ( b - a ) * L
也就是说i是圈长的整数倍。

这时a节点放在s起点，b处于N相遇位置,然后a,b同时向前走m步时，此时从头部走的指针在m位置。
b而\应该在距离起点i+m，i为圈长整数倍，则该指针也应该在距离起点为m的位置，即环的起点。
我们可以理解为b节点从起点开始走，走到环起点，然后绕环转了几圈。