题目描述

题目：寻找重复的数

在一个长度为 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 示例代码

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 示例代码

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 示例代码

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

码小课网站中有更多关于算法和数据结构的内容分享，欢迎大家学习交流。