您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode怎么查看数组中重复的数字
## 引言
在算法学习和编程面试中，**查找数组中重复数字**是一个经典且高频出现的问题。这类问题不仅考察基础编程能力，更检验开发者对数据结构、算法效率的掌握程度。本文将系统性地讲解在LeetCode环境中解决数组重复数字问题的多种方法，涵盖从暴力解法到最优算法的完整思路，帮助读者建立系统的解题框架。
## 问题定义与示例
### 基本问题描述
给定一个长度为n的整数数组，数组中所有数字都在0~n-1范围内。找出数组中任意一个重复的数字。
**示例1：**
```python
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2或3
通过两层循环逐个比较数组元素。
def findDuplicate(nums):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] == nums[j]:
return nums[i]
仅在小规模数据时可用，LeetCode中通常会超时。
利用哈希表存储已出现过的数字。
def findDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
def findDuplicate(nums):
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return nums[i]
利用数组索引和值的对应关系，通过交换元素到正确位置来发现重复。
def findDuplicate(nums):
i = 0
while i < len(nums):
if nums[i] == i:
i += 1
else:
if nums[nums[i]] == nums[i]:
return nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
特别适用于LeetCode 287（不修改数组且空间O(1)）
基于鸽巢原理，统计小于等于mid的数的个数。
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
将数组视为链表，用快慢指针找环的入口。
def findDuplicate(nums):
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
finder = 0
while finder != slow:
finder = nums[finder]
slow = nums[slow]
return finder
Phase 1: 确定相遇点
2→3→1→0→2→3→1...
slow: 2→1→3→0→2
fast: 2→3→0→1→3→0→1→3...
Phase 2: 找环入口
finder: 0→2→1
slow: 2→1→3
| 方法 | 时间复杂度 | 空间复杂度 | 是否修改原数组 | 适用场景 |
|---|---|---|---|---|
| 暴力循环 | O(n²) | O(1) | 否 | 小数据量 |
| 哈希表 | O(n) | O(n) | 否 | 通用解法 |
| 排序+遍历 | O(nlogn) | O(1) | 是 | 允许修改且不限空间 |
| 原地交换 | O(n) | O(1) | 是 | 数字范围在0~n-1 |
| 二分查找 | O(nlogn) | O(1) | 否 | 1~n范围且不修改数组 |
| 快慢指针 | O(n) | O(1) | 否 | 存在且仅存在一个重复数 |
要求：给定包含n+1个整数的数组，其数字在1到n之间（包括1和n），假设只有一个重复的整数，找出这个重复的数。
最优解：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# 快慢指针解法
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
finder = 0
while finder != slow:
finder = nums[finder]
slow = nums[slow]
return finder
要求：找出所有出现两次的元素。
解法：
def findDuplicates(nums):
res = []
for num in nums:
idx = abs(num) - 1
if nums[idx] < 0:
res.append(abs(num))
else:
nums[idx] = -nums[idx]
return res
索引越界问题：
无限循环：
边界条件：
# 测试用例
[1,1] # 最小重复
[2,2,2,2] # 多个重复
[1,3,4,2,2] # 标准情况
掌握查找数组重复数字的多种解法，有助于培养以下能力： - 根据题目约束选择最优算法 - 理解时间空间复杂度的权衡 - 灵活运用数据结构特性
建议按照以下顺序练习： 1. 先实现哈希表解法 2. 再尝试原地交换 3. 最后攻克快慢指针解法
提示：在LeetCode做题时，注意题目中的关键约束条件，如”不能修改原数组”、”空间复杂度O(1)“等，这些往往是解题方法的选择关键。 “`
（注：实际字数约2200字，此处显示为精简版框架，完整文章需展开各部分的详细说明和代码注释）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。