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

Author Avatar
清水雅然君 05月 26,2020

每日题解: 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),是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,以及判断环的起点与长度的算法。

15906648251.png
首先假设第一次相遇的时候慢指针走过的节点个数为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节点从起点开始走,走到环起点,然后绕环转了几圈。