提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

287. 寻找重复数

数组 映射
2023-04-18 16:12:42 时间

一. 题目:

二. 思路:

确定映射关系：数组下标 -> 数组值 有重复元素就意味着必然有两条不同起点的边映射到一个值上，即指向同一个点，因此就会产生环 [1,2,4,5,6,4,3]

index -> value

映射关系

形成了0->1->2->4->6->3->5->4->6->3的环形表

至此，问题转换为 142 题 环形链表。那么针对此题，快、慢指针该如何走呢。根据上述数组转链表的映射关系，可推出 142 题中慢指针走一步 slow = slow.next ==> 本题 slow = nums[slow] 142 题中快指针走两步 fast = fast.next.next ==> 本题 fast = nums[nums[fast]]

三. 代码:

class Solution {
    public int findDuplicate(int[] nums) {
        //快慢指针索引位置
        int slow=nums[0], fast=nums[nums[0]];

        //找到相遇结点
        while (nums[slow]!=nums[fast]){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }


        //找到起始结点
        fast=0;
        while (slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }

        return slow;
    }
}

相关文章