当前位置： 面试刷题>> 寻找重复的数 (经典算法题500道)
### 题目描述
**题目：寻找重复的数**
在一个长度为 n+1 的整数数组 `nums` 中，所有的数字都在 1 到 n 的范围内，所以数组中至少有一个数字是重复的。请找出任意一个重复的数字，但不能修改数组（即，只能使用额外的 O(1) 的空间）。
**示例 1**:
```
输入: [1,3,4,2,2]
输出: 2
```
**示例 2**:
```
输入: [3,1,3,4,2]
输出: 3
```
### 解题思路
由于题目要求只能使用 O(1) 的额外空间，且数组长度为 n+1，数字范围为 1 到 n，因此我们可以利用数组索引作为“哈希表”的映射来解决问题。遍历数组时，尝试将索引对应的元素值设为负数（或某种标记），如果发现该元素已经是负数（或已被标记），则说明找到了重复的数字。
但这种方法会修改原数组，不符合题目“不能修改数组”的要求。因此，我们可以使用数组中的值作为索引，将对应索引位置上的元素加上 n（或任何大于数组最大值的数），这样就不会影响原数组中的元素值范围，同时达到了标记的目的。
### PHP 示例代码
```php
function findDuplicate($nums) {
$n = count($nums) - 1;
for ($i = 0; $i < count($nums); $i++) {
$index = abs($nums[$i]) - 1;
if ($nums[$index] < 0) {
return abs($nums[$i]);
}
$nums[$index] = -$nums[$index];
}
// 理论上这里不应该到达，因为题目保证了至少有一个重复数字
return -1;
}
// 示例
$nums = [1, 3, 4, 2, 2];
echo findDuplicate($nums); // 输出 2
```
### Python 示例代码
```python
def findDuplicate(nums):
n = len(nums) - 1
for i in range(n + 1):
index = abs(nums[i]) - 1
if nums[index] < 0:
return abs(nums[i])
nums[index] = -nums[index]
# 理论上这里不应该到达，因为题目保证了至少有一个重复数字
return -1
# 示例
nums = [1, 3, 4, 2, 2]
print(findDuplicate(nums)) # 输出 2
```
### JavaScript 示例代码
```javascript
function findDuplicate(nums) {
const n = nums.length - 1;
for (let i = 0; i < nums.length; i++) {
const index = Math.abs(nums[i]) - 1;
if (nums[index] < 0) {
return Math.abs(nums[i]);
}
nums[index] = -nums[index];
}
// 理论上这里不应该到达，因为题目保证了至少有一个重复数字
return -1;
}
// 示例
const nums = [1, 3, 4, 2, 2];
console.log(findDuplicate(nums)); // 输出 2
```
**码小课**网站中有更多关于算法和数据结构的内容分享，欢迎大家学习交流。