LCR 120.寻找文件副本
难度：🟢 简单
标签：数组、哈希表、排序
链接：LCR 120. 寻找文件副本 (剑指 Offer 03. 数组中重复的数字)
题目描述
在一个长度为 n 的数组 documents 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
解题思路
核心思想
本题的核心是利用 “n 个数字都在 0～n-1 范围内” 这一关键信息。如果没有重复数字，那么排序后，数组中的每个数字 i 都会恰好出现在索引为 i 的位置。重复数字的存在打破了这种 “萝卜和坑” 的一一对应关系。
思路选择
哈希集合法：这是最直观的思路。遍历数组，使用一个哈希集合（Set）来记录已经出现过的数字。如果当前数字已存在于集合中，则说明找到了一个重复数字，直接返回。这是以空间换时间的典型方法。
原地交换法 (最优)：这是利用题目核心信息的最优解法，可以实现 O(1) 的空间复杂度。我们遍历数组，目标是将数字
i放到索引为i的位置上。当我们遍历到索引
i时，如果documents[i]的值不等于i，我们就把它和它应该在的位置documents[documents[i]]进行交换。在交换前，如果发现
documents[i]和documents[documents[i]]的值已经相等了，那就说明我们找到了一个重复的数字。
关键步骤 (原地交换法)
循环遍历：从索引
i = 0开始遍历数组。位置检查：在循环中，只要
documents[i]不等于i，就持续进行交换操作。查找与交换： a. 设
m = documents[i]。 b. 检查documents[m]的值。如果documents[m]已经等于m，说明数字m已经出现过一次（在索引i的位置），现在又在索引m的位置发现它，因此m就是一个重复数字，直接返回m。 c. 否则，交换documents[i]和documents[m]的值，将数字m放到它正确的位置上。继续循环：交换后，
documents[i]的值变了，继续内层while循环，直到documents[i] === i。
代码实现 (推荐 - 原地交换)
/**
* @param {number[]} documents
* @return {number}
*/
var findRepeatDocument = function(documents) {
for (let i = 0; i < documents.length; i++) {
// 当索引 i 的位置不是数字 i 时
while (documents[i] !== i) {
const m = documents[i];
// 如果数字 m 应该在的位置上已经是 m 了，说明 m 重复
if (documents[m] === m) {
return m;
}
// 否则，将数字 m 交换到正确的位置
[documents[i], documents[m]] = [documents[m], documents[i]];
}
}
// 根据题意，一定存在重复，此行理论上不会执行
return -1;
};
原始代码分析 (用户提供)
您提供的代码使用了哈希集合（Set）的方法，逻辑清晰，是解决此类问题的通用方案。
/**
* @param {number[]} documents
* @return {number}
*/
var findRepeatDocument = function (documents) {
// 使用 Set 记录出现过的数字
let set = new Set();
for (let i = 0; i < documents.length; i++) {
// 如果数字已存在于 Set 中，则为重复数字
if (set.has(documents[i])) return documents[i];
// 否则，将其加入 Set
else set.add(documents[i]);
}
};
优点：代码简洁，易于理解，并且对于没有
0～n-1范围限制的普通数组查找重复数问题同样适用。待改进：该方法使用了 O(n) 的额外空间来存储
Set。对于本题，由于有特殊的数字范围限制，存在空间复杂度为 O(1) 的更优解法（即原地交换法）。
复杂度分析
时间复杂度：O(n) 原地交换法虽然有嵌套循环，但每个数字最多只会被交换一次到其正确的位置，所以总的时间复杂度是线性的。
空间复杂度：O(1) 原地交换法只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题是考察对数组特性利用的经典题目。哈希法是通用解，而原地交换法则是在特定约束下（数字在 0～n-1 范围内）的、更优的时空复杂度解决方案，充分体现了算法设计中“利用问题约束”的重要性。