 时间 O(1) 空间的就地置换解法详解)
CS-Notes 剑指 Offer 3：数组中重复的数字——O(n) 时间 O(1) 空间的就地置换解法详解
【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes
本篇指南基于 CS-Notes 剑指 Offer 题解中的《3. 数组中重复的数字》(notes/3. 数组中重复的数字.md)展开，讲解一个在面试中出现频率极高的经典数组题：在长度为 n、元素全部落在 [0, n-1] 区间内的数组中找出任意一个重复数字，并满足时间复杂度 O(n)、空间复杂度 O(1) 的严苛限制。读完全文，你将掌握"值即下标"的**就地置换（In-Place Swap）**思想、原仓库参考实现的逐行解析与复杂度证明，并能举一反三地处理同一约束下的其它数组问题。
一、题目描述与输入输出
题目原文（继承自 notes/3. 数组中重复的数字.md）：
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
示例：
Input: {2, 3, 1, 0, 2, 5} Output: 2注意两个关键前提：
- 元素值域受限：所有数字都在 [0, n-1] 内。这是后续"值即下标"策略成立的前提；
- 只需找出任意一个重复数字即可，不要求找全、也不要求统计次数，这降低了问题的难度等级。
该题在牛客网的剑指 Offer 刷题专区中是"数组"分类的第一题，也是 剑指 Offer 题解目录 中"数组与矩阵"分类的开篇题，适合用来热身。
二、先排除两条"走不通"的常规路线
原文明确给出的约束是：要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。这里把三种常见思路放在一起对比，看清约束如何把解法空间压缩到"就地置换"：
| 思路 | 时间复杂度 | 空间复杂度 | 是否满足约束 |
|---|---|---|---|
哈希集合：遍历数组，set.contains(x)命中即返回 | O(n) 平均 | O(n) | 空间不满足 |
| 原地排序后扫描相邻元素 | O(n log n) | O(1) | 时间不满足 |
| 就地置换（本方案） | O(n) | O(1) | 满足 |
哈希集合法虽然代码最短，但额外开了 O(n) 的标记空间，直接违背 O(1) 空间要求；排序法空间虽省，但 O(n log n) 的时间达不到题目要求。剩下的唯一选择就是利用"值域 == 下标域"这一隐含结构。
三、核心思想：把值为 i 的元素交换到第 i 个位置
原文的解题思路（完整继承）：
对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。
换句话说，数组的理想终态是nums[i] == i对每个位置成立。遍历过程中不断执行"把nums[i]放到它值对应的位置"这一置换动作：
- 如果
nums[i]的目标位置上已经躺着一个相同的数，说明该数字至少出现了两次，可以直接返回； - 否则交换、继续，直到
nums[i] == i，再考察下一个下标。
以原文给出的 (2, 3, 1, 0, 2, 5) 为例，置换过程如下：
| 步骤 | 数组状态 | 动作 |
|---|---|---|
| 初始 | (2, 3, 1, 0, 2, 5) | 开始遍历 |
| i=0 | (1, 3, 2, 0, 2, 5) | 把 2 与下标 2 处的元素交换 |
| i=0 | (3, 1, 2, 0, 2, 5) | 把 1 与下标 1 处的元素交换 |
| i=0 | (0, 1, 2, 3, 2, 5) | 把 3 与下标 3 处的元素交换，此时 nums[0]==0，i 前移 |
| i=1~3 | (0, 1, 2, 3, 2, 5) | 位置 1、2、3 均已归位，跳过 |
| i=4 | (0, 1, 2, 3, 2, 5) | nums[4]=2，而 nums[2]=2，命中重复，返回 2 |
原文中的过程动图展示的就是这一交换推演：
正如原文所述："遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复。"
四、参考实现逐行解析
原仓库给出的 Java 参考实现如下（完整继承自 notes/3. 数组中重复的数字.md，此处补充了逐行注释）：
public int duplicate(int[] nums) { for (int i = 0; i < nums.length; i++) { // 当前下标 i 上的元素尚未归位（理想终态是 nums[i] == i） while (nums[i] != i) { // 核心判重：nums[i] 想去的下标 nums[i] 上已经躺着相同的值 if (nums[i] == nums[nums[i]]) { return nums[i]; } // 把 nums[i] 放到它值对应的下标上 swap(nums, i, nums[i]); } // 循环退出时 nums[i] == i，此处的 swap 是自我交换（无操作）， // 属于参考代码里的冗余语句，可安全删除 swap(nums, i, nums[i]); } return -1; // 题目保证存在重复数字时此分支不会执行；作为防御性返回值 } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }几个实现细节值得展开：
1. 为什么判重条件写成nums[i] == nums[nums[i]]？
当nums[i] != i时，nums[i]理应被换到下标nums[i]处。若那个位置上已经是同一个值（nums[nums[i]] == nums[i]），则同一个数字占据了两个位置，重复成立。由于值域限制在 [0, n-1]，nums[i]本身可以作为合法下标使用，不会越界——这是该写法成立的关键前提。
2. 时间复杂度为什么是严格的 O(n)？
外层循环看似有 n 次迭代、内层还有 while，但可以从"交换总量"角度证明：每次执行swap(nums, i, nums[i])，都会让下标nums[i]（即元素的目标位置）上的元素归位。一个元素最多被"正确落位"一次，因此整个算法过程中 swap 总次数不超过 n 次，内外层合计的常数工作量是 O(n)。同时没有任何额外数据结构，空间复杂度 O(1)（只用了栈上的临时变量t）。
3. 代码里的冗余语句
while 循环退出时必然有nums[i] == i，此时swap(nums, i, nums[i])等价于swap(nums, i, i)，是自我交换的无操作语句，实际作答时可以直接删掉，不影响正确性。另外return -1是防御性返回：若输入数组无重复（与题目"某些数字是重复的"的前提矛盾），函数不会误报，而是返回 -1。
4. 数组会被原地修改
该解法会改变输入数组的顺序，遍历结束后（或中途命中时）数组已部分置换。若调用方还需要原始顺序，应先复制一份——但那样会引入 O(n) 空间，与 O(1) 约束冲突，因此答题时应先确认题目是否允许原地修改；剑指 Offer 该题默认允许。
五、边界与易错点
- 首元素即为重复：如 (1, 2, 3, 4, 1, 6)，i=0 时
nums[0]=1，nums[1]=2不相等，先交换；随后 1 归位过程中再次遇到已有的 1，正确命中。可见判重发生在"落位前"，不会漏掉首元素重复； - 重复元素不止一个：题目只要求返回任意一个，算法遇到第一个"目标位已占用"的情况就立即返回，因此返回的是置换顺序中先暴露的那个重复值，而非字典序最小或出现次数最多的；
- 越界风险：只有当输入满足"元素均在 [0, n-1]"时才成立。若面试中出现元素超出下标范围（例如求任意重复值且值域为 [0, m]、m >= n），
nums[i]就不能直接当下标使用，此时应改用位图、Floyd 判圈（需额外条件）或哈希法，并主动向面试官确认约束； - 负数或 0 边界：0 是合法元素，
nums[0] == 0直接跳过即可，代码中 while 条件天然处理了这种情况。
六、思想迁移：仓库中的同族题目
就地置换并非孤立技巧，它是"值域与下标域重合"这一类数组题的通用钥匙，CS-Notes 仓库中有多题可与之对照：
- 调整数组顺序使奇数位于偶数前面：同样使用了一个
swap(int[] nums, int i, int j)三行交换辅助函数（写法与本题参考实现完全一致），其中方法二用"冒泡式"相邻交换在 O(1) 空间内完成重排，可与本题对照体会"不同置换目标（奇偶分区 vs 值即下标）下的交换策略"；
- 调整数组顺序使奇数位于偶数前面：同样使用了一个
- 数组中只出现一次的数字：同样是"数组中的数字"题，但它走的是位运算路线——全体异或得到
z ^ k，再用diff & -diff提取最低有效 1 位把数组分成两组二次异或。它与本题构成很好的思想对照：一个利用"值即下标"做空间换零开销，一个利用"相同值异或为 0"消除重复，面试时可以说清两者的适用前提差异（前者要求值域 == [0, n-1]，后者要求"恰好两个数出现一次、其余出现两次"）；
- 数组中只出现一次的数字：同样是"数组中的数字"题，但它走的是位运算路线——全体异或得到
- 更多同类约束下的题目（如 53. 数字在排序数组中出现的次数、39. 数组中出现次数超过一半的数字）可在 剑指 Offer 题解 - 目录 的"数组与矩阵""数学""位运算"分类中继续练习。
七、小结
| 维度 | 结论 |
|---|---|
| 适用前提 | 数组长度 n，所有元素值 ∈ [0, n-1] |
| 核心操作 | 每步把nums[i]置换到下标nums[i]，落位前检查nums[i] == nums[nums[i]]判重 |
| 时间复杂度 | O(n)，swap 总量 ≤ n 次 |
| 空间复杂度 | O(1)，仅栈上临时变量 |
| 副作用 | 原地修改数组顺序 |
| 失效场景 | 值域超出 [0, n-1]，需改用哈希/位图或向面试官确认约束 |
一句话记忆点：当数组的值域恰好等于下标域时，"让值回家"的置换过程本身就会把重复值撞出来。掌握这一模式后，遇到 O(n) 时间 + O(1) 空间的数组查找题，应优先检查题目是否满足"值域 == 下标域"这一隐含条件。
【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
