空间复杂度解决缺失正数问题)
在实际算法面试和刷题过程中原地哈希In-place Hashing是一种巧妙利用数组自身空间来存储额外信息从而将空间复杂度降至 O(1) 的高级技巧。它尤其适用于那些要求“不使用额外空间”或“空间复杂度为 O(1)”的数组类问题。原地哈希的核心思想是将数组的索引和值建立一种映射关系通过修改数组元素来标记某个信息通常是某个索引对应的值是否出现过之后再通过某种规则恢复原始值或直接得出答案。本文将围绕原地哈希这一核心技巧通过解析一道典型的 LeetCode 题目—— 41. 缺失的第一个正数 来深入讲解其原理、实现步骤、关键细节以及常见的易错点。我们将从理解问题本质开始逐步推导出原地哈希的解决方案并给出完整的代码实现、详细的逐行注释以及针对生产环境的扩展思考。1. 理解原地哈希解决的问题场景原地哈希并非一种通用的算法而是针对特定约束条件主要是严格的 O(1) 空间复杂度的优化手段。在开始编码之前必须清晰地理解它要解决的核心矛盾如何在不能使用额外数据结构如哈希表、集合的情况下高效地记录和查询信息。1.1 为什么常规哈希解法行不通对于“查找第一个缺失的正整数”这类问题最直观的解法是使用哈希集合HashSet。我们可以遍历一次数组将所有正整数放入集合中然后从 1 开始逐个检查哪个正整数不在集合中找到的第一个缺失的正整数就是答案。这种方法的时间复杂度是 O(N)空间复杂度也是 O(N)。然而问题要求空间复杂度为 O(1)这就直接排除了使用额外数据结构的可能。我们必须在不申请额外空间的前提下完成信息的“记录”和“查询”。1.2 原地哈希的可行性分析原地哈希之所以可行是基于一个关键的观察对于一个长度为 N 的数组缺失的第一个正数一定在 [1, N1] 这个范围内。如果数组包含了 1 到 N 的所有数字那么缺失的第一个正数就是 N1。如果数组缺失了 [1, N] 中的某个数字那么缺失的第一个正数一定在 [1, N] 之间。这个观察意味着我们只需要关心数组中值在 [1, N] 范围内的数字。我们可以利用数组索引本身从 0 到 N-1来表征数字 1 到 N 是否存在。具体来说如果数字x(1 ≤ x ≤ N) 在数组中出现过我们就可以在索引为x-1的位置做一个标记。1.3 标记策略的选择与恢复如何在原地做标记同时不丢失原始数据常见的策略有取负数将对应位置的元素取负数表示该索引对应的数字存在。前提是原始数组中的数字不能干扰标记通常需要先预处理将负数和不关心的数排除在标记体系外。交换位置通过交换元素将数字x放到索引x-1的位置上。这样最终如果某个索引i上的数字不是i1就说明i1这个数字缺失了。本文将重点讲解第二种策略——交换法因为它逻辑清晰且在实践中更为常用。2. 问题定义与算法思路我们以 LeetCode 41 题“缺失的第一个正数”为例详细阐述原地哈希交换法的完整思路。问题描述 给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。 要求时间复杂度为 O(N)空间复杂度为 O(1)。示例 1 输入nums [1, 2, 0] 输出3 解释数组中的正数有 1 和 2最小的缺失正数是 3。示例 2 输入nums [3, 4, -1, 1] 输出2 解释1 在数组中但 2 缺失。示例 3 输入nums [7, 8, 9, 11, 12] 输出1 解释最小的正数 1 就缺失了。2.1 核心算法步骤基于交换的原地哈希算法可以分为三个主要步骤“归位”操作遍历数组对于每个元素nums[i]如果它是一个在 [1, N] 范围内的正整数记作x并且它当前不在它“应该”在的位置上即nums[i]不等于nums[nums[i]-1]我们就将它交换到索引为x-1的位置上。这个过程可能需要循环进行因为被交换过来的新元素可能也需要被“归位”。扫描检查在完成“归位”操作后再次遍历数组。第一个满足nums[i] ! i1的位置i其对应的数字i1就是缺失的第一个正数。边界情况处理如果遍历完数组都没有找到nums[i] ! i1的情况说明数组包含了 1 到 N 的所有数字那么缺失的第一个正数就是 N1。2.2 为什么交换是有效的交换操作的本质是建立了一个隐式的映射索引 i 上的值应该是 i1。通过交换我们让所有值在 [1, N] 范围内的数字都尽可能地位于其对应的索引上即数字 1 在索引 0数字 2 在索引 1...数字 N 在索引 N-1。那些不在 [1, N] 范围内的数字负数、0、大于 N 的数会被交换到数组的某些位置但我们不关心它们最终在哪我们只关心 [1, N] 范围内的数字是否都“对号入座”了。3. 代码实现与逐行解析下面给出该算法的 Java 实现并附上详细的注释。public class Solution { public int firstMissingPositive(int[] nums) { int n nums.length; // 第一遍遍历进行“归位”操作 for (int i 0; i n; i) { // 使用 while 循环直到当前 i 位置上的数被交换成一个不需要再归位的数为止 // 条件1: nums[i] 是介于 1 和 n 之间的数才是我们关心的需要被归位 // 条件2: nums[i] 不应该等于它目标位置上的数否则交换无意义且可能死循环 // 例如如果 nums[i] x, 而 nums[x-1] 也等于 x说明 x 已经在正确位置了 while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1]) { // 交换 nums[i] 和它应该去的位置上的数 swap(nums, i, nums[i] - 1); } } // 第二遍遍历检查第一个“位置不对”的数 for (int i 0; i n; i) { // 如果索引 i 上的数字不是 i1说明 i1 这个正整数缺失了 if (nums[i] ! i 1) { return i 1; } } // 如果前 n 个位置都正确说明 1 到 n 都出现了缺失的是 n1 return n 1; } // 辅助函数交换数组中两个位置的元素 private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }3.1 关键代码段解析while循环条件nums[i] ! nums[nums[i] - 1] 这是避免死循环和无效交换的关键。假设nums[i] x。如果nums[x-1]已经等于x说明数字x已经在其正确的位置上了。此时如果再进行交换相当于把x换走又把x换回来是无用功如果nums[i]恰好也是x还会造成死循环。只有当nums[x-1]不是x时我们才需要交换目的是把x放到正确位置同时把错误位置的数拿到i这里来继续处理。为什么使用while而不是if 因为一次交换后被换到位置i的新数字原来是nums[x-1]可能也是一个需要被归位的在 [1, N] 范围内的数字。所以我们需要持续检查并交换直到位置i上的数字不再满足归位条件要么不在 [1, N] 范围内要么已经在正确位置上了。3.2 时间复杂度分析尽管代码中有嵌套循环但时间复杂度仍然是 O(N)。这是因为每个数字通过交换操作最多会被放置到其正确的位置上一次。整个过程中交换的总次数不会超过 N 次。因此均摊时间复杂度是 O(N)。4. 运行验证与测试用例为了确保算法的正确性需要设计全面的测试用例。测试用例输入 (nums)预期输出说明[1, 2, 0]3基础案例缺失3[3, 4, -1, 1]2基础案例缺失2包含负数和无序[7, 8, 9, 11, 12]1缺失1的边界案例[1]2单元素且为1缺失2[2]1单元素为2缺失1[]1空数组缺失1[1, 1]2包含重复元素缺失2我们可以编写一个简单的main函数来验证public static void main(String[] args) { Solution solution new Solution(); int[][] testCases { {1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}, {1}, {2}, {}, {1, 1} }; int[] expected {3, 2, 1, 2, 1, 1, 2}; for (int i 0; i testCases.length; i) { int result solution.firstMissingPositive(testCases[i]); System.out.printf(Input: %s - Output: %d, Expected: %d - %s\n, Arrays.toString(testCases[i]), result, expected[i], result expected[i] ? PASS : FAIL); } }5. 常见问题与排查指南在实际实现原地哈希算法时很容易遇到以下几个问题5.1 死循环问题现象程序无法终止卡在while循环中。原因通常是交换条件判断不严谨。例如如果只判断nums[i]是否在 [1, N] 内就进行交换而当nums[i]和nums[nums[i]-1]相等时交换它们没有意义并且如果此时i不等于nums[i]-1就会导致两个相等的值被反复交换形成死循环。解决严格使用while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1])作为条件。5.2 结果错误问题现象对于某些测试用例输出结果不正确。原因1忘记处理空数组的边界情况。如果数组为空按照算法n0第二遍遍历不会进入直接返回011这是正确的。但如果在代码开头加了不必要的判断可能会出错。原因2在第二遍遍历时判断条件写错。必须是if (nums[i] ! i 1)而不是if (nums[i] ! i)或其他。排查使用上文的测试用例逐一验证并使用调试工具跟踪数组在“归位”操作后的变化。5.3 索引越界问题现象出现ArrayIndexOutOfBoundsException。原因在计算目标索引nums[i] - 1时没有确保nums[i]是正数。如果nums[i]是负数或0nums[i] - 1是负数访问数组会越界。解决我们的while条件nums[i] 1已经保证了只有正数才会进入交换逻辑从而避免了越界。6. 原地哈希的变体与最佳实践6.1 取负数标记法对于某些问题如果原始数组的元素都是正数或者可以先预处理将负数变为不干扰标记的数可以使用取负数法。基本步骤是将所有的负数和大于 N 的数改为一个标记值如 N1使其不参与后续标记。遍历数组对于每个值x其绝对值在 [1, N] 范围内将索引为|x|-1的位置的元素变为负数表示数字|x|出现过。遍历数组第一个正数所在的索引i对应的i1就是缺失的第一个正数。这种方法同样满足 O(N) 时间和 O(1) 空间的要求但需要额外的预处理步骤且对原始数据有修改变为负数。6.2 生产环境中的考量虽然算法题要求 O(1) 空间但在实际生产环境中如果允许使用 O(N) 空间哈希集合法通常是更优选择因为代码可读性哈希集合的意图非常明确易于理解和维护。数据安全性不会修改原始输入数据。原地哈希会改变输入数组这在某些场景下是不可接受的。性能虽然时间复杂度相同但哈希集合的常数时间操作通常很快。只有当内存限制极其严格或者面试、考试有明确要求时才优先选择原地哈希法。6.3 适用问题类型原地哈希技巧通常适用于以下类型的数组问题查找重复/缺失的数字如本题、 442. 数组中重复的数据 。将数组元素按某种规则重排如 448. 找到所有数组中消失的数字 。掌握原地哈希的核心在于识别出“数组索引本身可以作为信息载体”这一模式。当遇到空间复杂度限制为 O(1) 的数组问题时应优先考虑原地哈希是否适用。
在实际算法面试和刷题过程中原地哈希In-place Hashing是一种巧妙利用数组自身空间来存储额外信息从而将空间复杂度降至 O(1) 的高级技巧。它尤其适用于那些要求“不使用额外空间”或“空间复杂度为 O(1)”的数组类问题。原地哈希的核心思想是将数组的索引和值建立一种映射关系通过修改数组元素来标记某个信息通常是某个索引对应的值是否出现过之后再通过某种规则恢复原始值或直接得出答案。本文将围绕原地哈希这一核心技巧通过解析一道典型的 LeetCode 题目—— 41. 缺失的第一个正数 来深入讲解其原理、实现步骤、关键细节以及常见的易错点。我们将从理解问题本质开始逐步推导出原地哈希的解决方案并给出完整的代码实现、详细的逐行注释以及针对生产环境的扩展思考。1. 理解原地哈希解决的问题场景原地哈希并非一种通用的算法而是针对特定约束条件主要是严格的 O(1) 空间复杂度的优化手段。在开始编码之前必须清晰地理解它要解决的核心矛盾如何在不能使用额外数据结构如哈希表、集合的情况下高效地记录和查询信息。1.1 为什么常规哈希解法行不通对于“查找第一个缺失的正整数”这类问题最直观的解法是使用哈希集合HashSet。我们可以遍历一次数组将所有正整数放入集合中然后从 1 开始逐个检查哪个正整数不在集合中找到的第一个缺失的正整数就是答案。这种方法的时间复杂度是 O(N)空间复杂度也是 O(N)。然而问题要求空间复杂度为 O(1)这就直接排除了使用额外数据结构的可能。我们必须在不申请额外空间的前提下完成信息的“记录”和“查询”。1.2 原地哈希的可行性分析原地哈希之所以可行是基于一个关键的观察对于一个长度为 N 的数组缺失的第一个正数一定在 [1, N1] 这个范围内。如果数组包含了 1 到 N 的所有数字那么缺失的第一个正数就是 N1。如果数组缺失了 [1, N] 中的某个数字那么缺失的第一个正数一定在 [1, N] 之间。这个观察意味着我们只需要关心数组中值在 [1, N] 范围内的数字。我们可以利用数组索引本身从 0 到 N-1来表征数字 1 到 N 是否存在。具体来说如果数字x(1 ≤ x ≤ N) 在数组中出现过我们就可以在索引为x-1的位置做一个标记。1.3 标记策略的选择与恢复如何在原地做标记同时不丢失原始数据常见的策略有取负数将对应位置的元素取负数表示该索引对应的数字存在。前提是原始数组中的数字不能干扰标记通常需要先预处理将负数和不关心的数排除在标记体系外。交换位置通过交换元素将数字x放到索引x-1的位置上。这样最终如果某个索引i上的数字不是i1就说明i1这个数字缺失了。本文将重点讲解第二种策略——交换法因为它逻辑清晰且在实践中更为常用。2. 问题定义与算法思路我们以 LeetCode 41 题“缺失的第一个正数”为例详细阐述原地哈希交换法的完整思路。问题描述 给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。 要求时间复杂度为 O(N)空间复杂度为 O(1)。示例 1 输入nums [1, 2, 0] 输出3 解释数组中的正数有 1 和 2最小的缺失正数是 3。示例 2 输入nums [3, 4, -1, 1] 输出2 解释1 在数组中但 2 缺失。示例 3 输入nums [7, 8, 9, 11, 12] 输出1 解释最小的正数 1 就缺失了。2.1 核心算法步骤基于交换的原地哈希算法可以分为三个主要步骤“归位”操作遍历数组对于每个元素nums[i]如果它是一个在 [1, N] 范围内的正整数记作x并且它当前不在它“应该”在的位置上即nums[i]不等于nums[nums[i]-1]我们就将它交换到索引为x-1的位置上。这个过程可能需要循环进行因为被交换过来的新元素可能也需要被“归位”。扫描检查在完成“归位”操作后再次遍历数组。第一个满足nums[i] ! i1的位置i其对应的数字i1就是缺失的第一个正数。边界情况处理如果遍历完数组都没有找到nums[i] ! i1的情况说明数组包含了 1 到 N 的所有数字那么缺失的第一个正数就是 N1。2.2 为什么交换是有效的交换操作的本质是建立了一个隐式的映射索引 i 上的值应该是 i1。通过交换我们让所有值在 [1, N] 范围内的数字都尽可能地位于其对应的索引上即数字 1 在索引 0数字 2 在索引 1...数字 N 在索引 N-1。那些不在 [1, N] 范围内的数字负数、0、大于 N 的数会被交换到数组的某些位置但我们不关心它们最终在哪我们只关心 [1, N] 范围内的数字是否都“对号入座”了。3. 代码实现与逐行解析下面给出该算法的 Java 实现并附上详细的注释。public class Solution { public int firstMissingPositive(int[] nums) { int n nums.length; // 第一遍遍历进行“归位”操作 for (int i 0; i n; i) { // 使用 while 循环直到当前 i 位置上的数被交换成一个不需要再归位的数为止 // 条件1: nums[i] 是介于 1 和 n 之间的数才是我们关心的需要被归位 // 条件2: nums[i] 不应该等于它目标位置上的数否则交换无意义且可能死循环 // 例如如果 nums[i] x, 而 nums[x-1] 也等于 x说明 x 已经在正确位置了 while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1]) { // 交换 nums[i] 和它应该去的位置上的数 swap(nums, i, nums[i] - 1); } } // 第二遍遍历检查第一个“位置不对”的数 for (int i 0; i n; i) { // 如果索引 i 上的数字不是 i1说明 i1 这个正整数缺失了 if (nums[i] ! i 1) { return i 1; } } // 如果前 n 个位置都正确说明 1 到 n 都出现了缺失的是 n1 return n 1; } // 辅助函数交换数组中两个位置的元素 private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }3.1 关键代码段解析while循环条件nums[i] ! nums[nums[i] - 1] 这是避免死循环和无效交换的关键。假设nums[i] x。如果nums[x-1]已经等于x说明数字x已经在其正确的位置上了。此时如果再进行交换相当于把x换走又把x换回来是无用功如果nums[i]恰好也是x还会造成死循环。只有当nums[x-1]不是x时我们才需要交换目的是把x放到正确位置同时把错误位置的数拿到i这里来继续处理。为什么使用while而不是if 因为一次交换后被换到位置i的新数字原来是nums[x-1]可能也是一个需要被归位的在 [1, N] 范围内的数字。所以我们需要持续检查并交换直到位置i上的数字不再满足归位条件要么不在 [1, N] 范围内要么已经在正确位置上了。3.2 时间复杂度分析尽管代码中有嵌套循环但时间复杂度仍然是 O(N)。这是因为每个数字通过交换操作最多会被放置到其正确的位置上一次。整个过程中交换的总次数不会超过 N 次。因此均摊时间复杂度是 O(N)。4. 运行验证与测试用例为了确保算法的正确性需要设计全面的测试用例。测试用例输入 (nums)预期输出说明[1, 2, 0]3基础案例缺失3[3, 4, -1, 1]2基础案例缺失2包含负数和无序[7, 8, 9, 11, 12]1缺失1的边界案例[1]2单元素且为1缺失2[2]1单元素为2缺失1[]1空数组缺失1[1, 1]2包含重复元素缺失2我们可以编写一个简单的main函数来验证public static void main(String[] args) { Solution solution new Solution(); int[][] testCases { {1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}, {1}, {2}, {}, {1, 1} }; int[] expected {3, 2, 1, 2, 1, 1, 2}; for (int i 0; i testCases.length; i) { int result solution.firstMissingPositive(testCases[i]); System.out.printf(Input: %s - Output: %d, Expected: %d - %s\n, Arrays.toString(testCases[i]), result, expected[i], result expected[i] ? PASS : FAIL); } }5. 常见问题与排查指南在实际实现原地哈希算法时很容易遇到以下几个问题5.1 死循环问题现象程序无法终止卡在while循环中。原因通常是交换条件判断不严谨。例如如果只判断nums[i]是否在 [1, N] 内就进行交换而当nums[i]和nums[nums[i]-1]相等时交换它们没有意义并且如果此时i不等于nums[i]-1就会导致两个相等的值被反复交换形成死循环。解决严格使用while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1])作为条件。5.2 结果错误问题现象对于某些测试用例输出结果不正确。原因1忘记处理空数组的边界情况。如果数组为空按照算法n0第二遍遍历不会进入直接返回011这是正确的。但如果在代码开头加了不必要的判断可能会出错。原因2在第二遍遍历时判断条件写错。必须是if (nums[i] ! i 1)而不是if (nums[i] ! i)或其他。排查使用上文的测试用例逐一验证并使用调试工具跟踪数组在“归位”操作后的变化。5.3 索引越界问题现象出现ArrayIndexOutOfBoundsException。原因在计算目标索引nums[i] - 1时没有确保nums[i]是正数。如果nums[i]是负数或0nums[i] - 1是负数访问数组会越界。解决我们的while条件nums[i] 1已经保证了只有正数才会进入交换逻辑从而避免了越界。6. 原地哈希的变体与最佳实践6.1 取负数标记法对于某些问题如果原始数组的元素都是正数或者可以先预处理将负数变为不干扰标记的数可以使用取负数法。基本步骤是将所有的负数和大于 N 的数改为一个标记值如 N1使其不参与后续标记。遍历数组对于每个值x其绝对值在 [1, N] 范围内将索引为|x|-1的位置的元素变为负数表示数字|x|出现过。遍历数组第一个正数所在的索引i对应的i1就是缺失的第一个正数。这种方法同样满足 O(N) 时间和 O(1) 空间的要求但需要额外的预处理步骤且对原始数据有修改变为负数。6.2 生产环境中的考量虽然算法题要求 O(1) 空间但在实际生产环境中如果允许使用 O(N) 空间哈希集合法通常是更优选择因为代码可读性哈希集合的意图非常明确易于理解和维护。数据安全性不会修改原始输入数据。原地哈希会改变输入数组这在某些场景下是不可接受的。性能虽然时间复杂度相同但哈希集合的常数时间操作通常很快。只有当内存限制极其严格或者面试、考试有明确要求时才优先选择原地哈希法。6.3 适用问题类型原地哈希技巧通常适用于以下类型的数组问题查找重复/缺失的数字如本题、 442. 数组中重复的数据 。将数组元素按某种规则重排如 448. 找到所有数组中消失的数字 。掌握原地哈希的核心在于识别出“数组索引本身可以作为信息载体”这一模式。当遇到空间复杂度限制为 O(1) 的数组问题时应优先考虑原地哈希是否适用。
