【力扣热题100】287. 寻找重复数（弗洛伊德的乌龟和兔子方法）

【力扣热题100】287. 寻找重复数

• 写在最前面
• 理解解决 "寻找重复数" 问题的算法
• • 问题描述
  • 弗洛伊德的乌龟和兔子方法
  • • 为什么这个方法有效？
    • 代码
    • 复杂度
    • 总结回顾

      写在最前面

      刷一道力扣热题100吧

      难度中等

      https://leetcode.cn/problems/find-the-duplicate-number/?envType=study-plan-v2&envId=top-100-liked

      一年半前做过这题，但是时间复杂度不够。现在重新学一下

      主要是用到了弗洛伊德的乌龟和兔子方法

      算法预览：

      1. 初始化：从两个指针开始，“乌龟"和"兔子”，都指向第一个元素。

      2. 第一阶段 - 检测循环：每次移动乌龟一步（tortoise = nums[tortoise]），兔子两步（hare = nums[nums[hare]]）。继续这个过程，直到他们在循环中相遇。

      3. 第二阶段 - 找到循环的入口：将乌龟重置到数组的开头。将乌龟和兔子都每次移动一步。他们再次相遇的地方就是循环的入口，对应着重复的数字。

      

      理解解决 “寻找重复数” 问题的算法

      在处理 “287. 寻找重复数” 这个问题时，我们面临一个独特的挑战：在不修改数组并且只使用常数额外空间的情况下找出数组中的一个重复数字。

      这种情况使得传统的方法，如排序或哈希表变得不可行。

      然而，有一种巧妙的方法可以解决这个问题，这就是著名的弗洛伊德的乌龟和兔子算法，一种用于检测循环的方法。

      问题描述

      给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

      假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

      你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

      示例 1：

      输入：nums = [1,3,4,2,2]

      输出：2

      示例 2：

      输入：nums = [3,1,3,4,2]

      输出：3

      提示：

      • 1