网站开发维护干嘛,做网站的需求调研,赣州网站建设专家,菜鸟教程网站是怎么做的龟兔赛跑算法#xff08;Floyd’s Cycle-Finding Algorithm#xff09;寻找重复数
问题描述
给定一个长度为 N1 的数组 nums#xff0c;其中每个元素的值都在 [1, N] 范围内。根据鸽巢原理#xff0c;至少有一个数字是重复的。请找出这个重复的数字。
要求#xff1a; …龟兔赛跑算法Floyd’s Cycle-Finding Algorithm寻找重复数
问题描述
给定一个长度为 N1 的数组 nums其中每个元素的值都在 [1, N] 范围内。根据鸽巢原理至少有一个数字是重复的。请找出这个重复的数字。
要求
时间复杂度 O(N)空间复杂度 O(1)不能使用哈希表等额外存储 算法思路龟兔赛跑法
我们可以将数组视为一个链表其中 nums[i] 表示 i → nums[i] 的边。由于存在重复数字这个链表必然存在一个环而环的入口就是重复的数字。
步骤 快慢指针找相遇点判断是否有环 慢指针 slow 每次走 1 步slow nums[slow]快指针 fast 每次走 2 步fast nums[nums[fast]]直到 slow fast说明两者在环内相遇。 找环的入口即重复的数字 将 fast 重置到起点 0。slow 和 fast 都每次走 1 步直到再次相遇相遇点就是重复的数字。 代码实现
public int findDuplicate(int[] nums) {int slow 0;int fast 0;// 第一阶段快慢指针找相遇点do {slow nums[slow]; // 慢指针走 1 步fast nums[nums[fast]]; // 快指针走 2 步} while (slow ! fast);// 第二阶段找环的入口重复数字fast 0;while (slow ! fast) {slow nums[slow];fast nums[fast];}return slow; // 或 fast此时它们相等
}为什么这个算法有效 第一阶段找相遇点 假设环的长度为 L环外长度为 F。当 slow 进入环时fast 已经在环内且距离 slow 为 d0 ≤ d L。由于 fast 每次比 slow 多走 1 步它们会在 L - d 步后相遇。 第二阶段找环入口 设 slow 和 fast 在环内相遇时slow 走了 F a 步a 是环内走的步数。fast 走了 F a kL 步k 是整数因为 fast 可能绕环多圈。由于 fast 速度是 slow 的 2 倍 [ 2(F a) F a kL \implies F a kL \implies F kL - a ]这意味着从起点走 F 步刚好到达环的入口即重复数字。 示例
输入 nums [1, 3, 4, 2, 2] 步骤
第一阶段 slow 0 → 1 → 3 → 2 → 4 → 2 → 4 → ...fast 0 → 1 → 3 → 2 → 4 → 2 → 4 → ...它们在 2 或 4 相遇具体取决于实现。 第二阶段 fast 重置到 0然后 slow 和 fast 都每次走 1 步 fast 0 → 1 → 3 → 2slow 4 → 2 它们在 2 相遇因此 2 是重复数字。 复杂度分析
时间复杂度O(N)最多遍历 2N 次。空间复杂度O(1)仅用两个指针。 总结
龟兔赛跑算法是一种高效的链表环检测方法适用于
检测链表是否有环。找出数组中的重复数字数组值在 [1, N] 范围内。不修改原数组且满足 O(1) 额外空间。
