寻找重复数 - LeetCode 287 题解笔记
问题描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），已知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。
要求：
- 不修改数组 nums
- 只使用常量级 O(1) 的额外空间
解题思路
方法一：快慢指针法（Floyd判圈算法）
核心思想
将数组视为链表，利用快慢指针检测环的存在并找到环的入口：
-
数组映射为链表：
- 索引作为节点
- 数组值作为指向下一个节点的指针
-
重复数字必然形成环：
- 因为多个索引指向同一个值
- 例如 nums = [1,3,4,2,2] → 0→1→3→2→4→2→4→…（在2和4之间形成环）
算法步骤
-
第一阶段：检测环
- 快指针每次走两步，慢指针每次走一步
- 当两者相遇时，确认存在环
-
第二阶段：找到环入口
- 将慢指针重置到起点
- 快慢指针改为每次各走一步
- 再次相遇点即为重复数字
class Solution {public int findDuplicate(int[] nums) {// 初始都从第一个元素开始int slow = nums[0];int fast = nums[0];// 第一阶段：找到相遇点do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);// 第二阶段：找到环的入口slow = nums[0];while (slow != fast) {slow = nums[slow];fast = nums[fast]; // 这里应该是单步移动，不是双步}return slow;}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法二：二分查找法
核心思想
利用抽屉原理进行二分查找：
-
数值范围二分：
- 在[1,n]范围内二分
- 统计小于等于mid的数的个数
-
调整搜索范围：
- 如果计数 > mid，说明重复数在左半区
- 否则在右半区
class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();int l = 1, r = n - 1, ans = -1;while (l <= r) {int mid = (l + r) >> 1;int cnt = 0;for (int i = 0; i < n; ++i) {cnt += nums[i] <= mid;}if (cnt <= mid) {l = mid + 1;} else {r = mid - 1;ans = mid;}}return ans;}
};
复杂度分析
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
关键点说明
-
为什么快慢指针能工作：
- 重复数字导致多个节点指向同一个节点
- 形成环后，快指针最终会追上慢指针
-
边界条件处理：
- 数组长度至少为2（因n≥1）
- 保证只有一个重复数字
-
与常规链表环检测的区别：
- 不需要实际构建链表
- 直接利用数组索引和值的映射关系
