您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode如何寻找重复数
## 问题概述
在LeetCode的算法题库中，"寻找重复数"（Find the Duplicate Number）是一个经典的数组处理问题。题目要求在一个包含n+1个整数的数组中找到唯一的重复数字，所有数字都在1到n的范围内（包括1和n）。根据鸽巢原理，至少有一个数字是重复的。
### 问题描述
给定一个包含n + 1个整数的数组nums，其中每个整数都在[1, n]范围内。假设nums中只有一个重复的整数，返回这个重复的数。要求：
- 不能修改原数组（假设数组是只读的）
- 只能使用O(1)的额外空间
- 时间复杂度应低于O(n²)
## 常见解法分析
### 方法一：排序法（不符合要求）
最简单的方法是先对数组排序，然后遍历查找相邻的相同元素。虽然实现简单，但：
- 修改了原数组（违反条件1）
- 排序时间复杂度为O(n log n)
- 空间复杂度可能为O(1)或O(n)取决于排序实现
```python
# 不推荐的方法示例
def findDuplicate(nums):
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return nums[i]
使用哈希集合记录已出现的数字： - 时间复杂度O(n) - 空间复杂度O(n)（违反条件2）
# 不符合空间要求的解法
def findDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
将数组视为链表，利用Floyd判圈算法： 1. 将数组值看作指针（如nums[i]表示节点i指向nums[i]） 2. 因为有重复数字，所以必然存在环 3. 找到环的入口即为重复数字
第一阶段：检测环的存在
第二阶段：找到环的入口
def findDuplicate(nums):
# 第一阶段：寻找相遇点
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# 第二阶段：寻找环入口
fast = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
当题目允许修改数组或需要其他思路时，可以考虑二分查找变种
def findDuplicate(nums):
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
通过比较每一位上1的期望数量和实际数量来找出重复数
def findDuplicate(nums):
n = len(nums) - 1
duplicate = 0
for bit in range(32):
mask = 1 << bit
expected = actual = 0
for i in range(n + 1):
expected += 1 if (i & mask) else 0
actual += 1 if (nums[i] & mask) else 0
if actual > expected:
duplicate |= mask
return duplicate
| 方法 | 时间复杂度 | 空间复杂度 | 是否修改原数组 |
|---|---|---|---|
| 排序法 | O(n log n) | O(1) | 是 |
| 哈希表法 | O(n) | O(n) | 否 |
| 快慢指针法 | O(n) | O(1) | 否 |
| 二分查找法 | O(n log n) | O(1) | 否 |
| 位运算法 | O(n log n) | O(1) | 否 |
在实际面试中，快慢指针法是最优解，因为它满足所有约束条件且效率最高。理解这个算法需要掌握链表环检测的相关知识，建议结合LeetCode 142（环形链表II）一起练习。
掌握这些算法不仅能解决特定问题，更能培养将数组视为链表等抽象思维能力，这对解决其他复杂算法问题大有裨益。 “`
（注：实际字数为约1100字，可根据需要适当增减示例或详细说明部分以达到精确字数要求）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。