Article / 文章
LeetCode 第287题：寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
📖 文章摘要
本文详细解析LeetCode第287题“寻找重复数”，这是一道考察数组和二分查找的中等难度题目。文章提供了二分查找和快慢指针两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习数组操作和查找算法的读者。
核心知识点： 二分查找、快慢指针、数组操作
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升数组操作和查找算法能力的开发者
题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例
示例 1：
输入：nums = [1,3,4,2,2]
输出：2示例 2：
输入：nums = [3,1,3,4,2]
输出：3示例 3：
输入：nums = [1,1]
输出：1提示
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
解题思路
本题可以使用两种方法来实现：
-
二分查找：
- 在1到n的范围内进行二分查找
- 统计小于等于mid的数的个数
- 根据统计结果调整搜索范围
-
快慢指针：
- 将数组视为链表
- 使用快慢指针找到环的入口
- 环的入口即为重复数
图解思路
二分查找过程分析表
| 步骤 | 左边界 | 右边界 | 中间值 | 小于等于mid的个数 | 说明 |
|---|---|---|---|---|---|
| 初始 | 1 | 4 | 2 | 3 | 开始二分查找 |
| 1 | 1 | 2 | 1 | 1 | 向左搜索 |
| 2 | 2 | 2 | 2 | 3 | 找到重复数 |
快慢指针分析表
| 步骤 | 快指针 | 慢指针 | 说明 |
|---|---|---|---|
| 初始 | 0 | 0 | 开始移动 |
| 1 | 3 | 1 | 第一次移动 |
| 2 | 2 | 3 | 第二次移动 |
| 3 | 3 | 2 | 相遇点 |
| 4 | 2 | 2 | 找到重复数 |
代码实现
C# 实现
public class Solution {
// 二分查找解法
public int FindDuplicate(int[] nums) {
int left = 1;
int right = nums.Length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
// 统计小于等于mid的数的个数
foreach (int num in nums) {
if (num <= mid) {
count++;
}
}
if (count > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 快慢指针解法
public int FindDuplicate2(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;
}
}Python 实现
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# 二分查找解法
left, right = 1, len(nums) - 1
while left < right:
mid = (left + right) // 2
count = sum(1 for num in nums if num <= mid)
if count > mid:
right = mid
else:
left = mid + 1
return left
def findDuplicate2(self, nums: List[int]) -> int:
# 快慢指针解法
slow = fast = nums[0]
# 找到相遇点
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# 找到环的入口
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowC++ 实现
class Solution {
public:
// 二分查找解法
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
// 统计小于等于mid的数的个数
for (int num : nums) {
if (num <= mid) {
count++;
}
}
if (count > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 快慢指针解法
int findDuplicate2(vector<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;
}
};执行结果
C# 实现
- 执行用时：156 ms
- 内存消耗：35.2 MB
Python 实现
- 执行用时：132 ms
- 内存消耗：16.8 MB
C++ 实现
- 执行用时：48 ms
- 内存消耗：14.2 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 156 ms | 35.2 MB | 代码结构清晰，性能适中 |
| Python | 132 ms | 16.8 MB | 代码最简洁，性能不错 |
| C++ | 48 ms | 14.2 MB | 性能最优，内存占用最小 |
代码亮点
- 🎯 两种解法各有特点，适应不同场景
- 💡 二分查找解法不修改原数组
- 🔍 快慢指针解法空间复杂度为O(1)
- 🎨 代码结构清晰，易于理解
常见错误分析
- 🚫 未考虑数组边界条件
- 🚫 二分查找范围错误
- 🚫 快慢指针移动逻辑错误
- 🚫 统计计数逻辑错误
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 二分查找 | O(nlogn) | O(1) | 不修改原数组 | 时间复杂度较高 |
| 快慢指针 | O(n) | O(1) | 最优时间复杂度 | 需要理解链表环 |
相关题目
- LeetCode 142. 环形链表 II - 中等
- LeetCode 268. 丢失的数字 - 简单
- LeetCode 448. 找到所有数组中消失的数字 - 简单
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第287题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！