 时间 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)开始遍历i0(1, 3, 2, 0, 2, 5)把 2 与下标 2 处的元素交换i0(3, 1, 2, 0, 2, 5)把 1 与下标 1 处的元素交换i0(0, 1, 2, 3, 2, 5)把 3 与下标 3 处的元素交换此时 nums[0]0i 前移i1~3(0, 1, 2, 3, 2, 5)位置 1、2、3 均已归位跳过i4(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)i0 时nums[0]1nums[1]2不相等先交换随后 1 归位过程中再次遇到已有的 1正确命中。可见判重发生在落位前不会漏掉首元素重复重复元素不止一个题目只要求返回任意一个算法遇到第一个目标位已占用的情况就立即返回因此返回的是置换顺序中先暴露的那个重复值而非字典序最小或出现次数最多的越界风险只有当输入满足元素均在 [0, n-1]时才成立。若面试中出现元素超出下标范围例如求任意重复值且值域为 [0, m]、m nnums[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），仅供参考
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)开始遍历i0(1, 3, 2, 0, 2, 5)把 2 与下标 2 处的元素交换i0(3, 1, 2, 0, 2, 5)把 1 与下标 1 处的元素交换i0(0, 1, 2, 3, 2, 5)把 3 与下标 3 处的元素交换此时 nums[0]0i 前移i1~3(0, 1, 2, 3, 2, 5)位置 1、2、3 均已归位跳过i4(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)i0 时nums[0]1nums[1]2不相等先交换随后 1 归位过程中再次遇到已有的 1正确命中。可见判重发生在落位前不会漏掉首元素重复重复元素不止一个题目只要求返回任意一个算法遇到第一个目标位已占用的情况就立即返回因此返回的是置换顺序中先暴露的那个重复值而非字典序最小或出现次数最多的越界风险只有当输入满足元素均在 [0, n-1]时才成立。若面试中出现元素超出下标范围例如求任意重复值且值域为 [0, m]、m nnums[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），仅供参考
