龟兔赛跑算法（Floyd‘s Cycle-Finding Algorithm）寻找重复数

龟兔赛跑算法（Floyd’s Cycle-Finding Algorithm）寻找重复数

问题描述

给定一个长度为 N+1 的数组 nums，其中每个元素的值都在 [1, N] 范围内。根据鸽巢原理，至少有一个数字是重复的。请找出这个重复的数字。

要求：

• 时间复杂度 O(N)
• 空间复杂度 O(1)（不能使用哈希表等额外存储）

算法思路（龟兔赛跑法）

我们可以将数组视为一个链表，其中 nums[i] 表示 i → nums[i] 的边。由于存在重复数字，这个链表必然存在一个环，而环的入口就是重复的数字。

步骤：

1. 快慢指针找相遇点（判断是否有环）：

   • 慢指针 slow 每次走 1 步：slow = nums[slow]
   • 快指针 fast 每次走 2 步：fast = nums[nums[fast]]
   • 直到 slow == fast，说明两者在环内相遇。

2. 找环的入口（即重复的数字）：

   • 将 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，此时它们相等
}

为什么这个算法有效？

1. 第一阶段（找相遇点）：

   • 假设环的长度为 L，环外长度为 F。
   • 当 slow 进入环时，fast 已经在环内，且距离 slow 为 d（0 ≤ d < L）。
   • 由于 fast 每次比 slow 多走 1 步，它们会在 L - d 步后相遇。

2. 第二阶段（找环入口）：

   • 设 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]
步骤：

1. 第一阶段：
   • slow = 0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
   • fast = 0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
   • 它们在 2 或 4 相遇（具体取决于实现）。
2. 第二阶段：
   • fast 重置到 0，然后 slow 和 fast 都每次走 1 步：
     • fast = 0 → 1 → 3 → 2
     • slow = 4 → 2
   • 它们在 2 相遇，因此 2 是重复数字。

复杂度分析

• 时间复杂度：O(N)（最多遍历 2N 次）。
• 空间复杂度：O(1)（仅用两个指针）。

总结

龟兔赛跑算法是一种高效的链表环检测方法，适用于：

• 检测链表是否有环。
• 找出数组中的重复数字（数组值在 [1, N] 范围内）。
• 不修改原数组，且满足 O(1) 额外空间。