LeetCode热题100--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

示例 3 :
输入：nums = [3,3,3,3,3]
输出：3

题解

classSolution{publicintfindDuplicate(int[]nums){intslow=0;intfast=0;slow=nums[slow];fast=nums[nums[fast]];while(slow!=fast){slow=nums[slow];fast=nums[nums[fast]];}intpre1=0;intpre2=slow;while(pre1!=pre2){pre1=nums[pre1];pre2=nums[pre2];}returnpre1;}}

解析

出自：287.寻找重复数

classSolution{publicintfindDuplicate(int[]nums){// 初始化快慢指针，都从索引 0 开始// 注意：这里不是从 nums[0] 开始赋值，而是先设为 0（下标）intslow=0;intfast=0;// 先走一步，避免 while 循环一开始 slow == fast 跳过// 慢指针走一步：slow = nums[slow]slow=nums[slow];// 快指针走两步：fast = nums[nums[fast]]fast=nums[nums[fast]];// 第一阶段：使用 Floyd 判圈算法，找到环中的相遇点// 条件：只要 slow 和 fast 没相遇，就继续移动while(slow!=fast){slow=nums[slow];// 慢指针每次走 1 步fast=nums[nums[fast]];// 快指针每次走 2 步}// 第二阶段：找环的入口（即重复的数字）// pre1 从数组起点（下标 0）出发intpre1=0;// pre2 从第一阶段的相遇点出发intpre2=slow;// 当两个指针未相遇时，各自每次走 1 步while(pre1!=pre2){pre1=nums[pre1];// pre1 向前走一步pre2=nums[pre2];// pre2 向前走一步}// 相遇点即为环的入口，也就是重复的数字// 返回任意一个指针的值（pre1 或 pre2）returnpre1;}}