java数据结构与算法刷题-----LeetCode287. 寻找重复数-Toy模板网

这篇具有很好参考价值的文章主要介绍了java数据结构与算法刷题-----LeetCode287. 寻找重复数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

解题思路

弗洛伊德判圈法，也就是快慢指针判圈法（龟兔赛跑算法），此算法分为两个步骤

判断是否有环，并得到快慢指针相遇的结点：慢指针每次走一格，快指针每次走两格，只要有环，必然会相遇。

获取构成环的结点：相遇后，让慢指针归0，快指针继续呆在相遇的地方，然后两个人依次一格一格的后移，最终再次相遇的地方，就是构成环的地方。

本题是数组题，如何想到用环形链表的解法呢？

首先，这个题的数组，下标范围和取值范围是几乎相同的。因为下标范围在0 ~ n。取值范围是1 ~ n。那么下标和元素值是可以联立的。我们可以设置链表结点为[下标，元素值]来构成链表。因为有重复的元素值，那么这个链表比如有环，图解如下：

既然抽象出了链表，就可以使用弗洛伊德判圈法，先判断是否有环，然后获取相遇结点位置。下面给出两个例子

获取了相遇结点后，接下来就是慢指针归0，快指针继续在相遇的结点。然后两个指针依次一格一格的后移即可。图解如下

代码:时间复杂度O(n) 空间复杂度O(1)

文章来源地址https://www.toymoban.com/news/detail-821993.html

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;//快慢指针
        //将数组转换为链表，nums数组下标作为链表结点。对应下标的元素值作为指向下一个结点的指针
        //因此，只要数组中有重复元素，那么这个链表一定有环
        do{
            slow = nums[slow];//相当于 slow = slow.next
            fast = nums[nums[fast]];//相当于fast = fast.next.next;
        }while(slow != fast);//找到环，并指向相遇结点
        //然后slow归0，fast不变，依次后移，找到构成环的结点
        slow = 0;//slow归0
        while(slow != fast){//一格一格的后移，直到再次相遇，就是环的入口
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;//最终返回这个结点值
    }
}