空间复杂度解决数组查找问题)
如果你正在准备算法面试或者刷过 LeetCode 的数组类题目很可能遇到过这样的场景题目要求找出数组中缺失的第一个正数或者找出重复的数字但附加条件往往是时间复杂度 O(n)空间复杂度 O(1)。这种限制意味着你不能使用额外的哈希表来存储元素也不能对数组进行排序排序通常需要 O(n log n) 时间。这时候原地哈希In-place Hashing就成为了解决问题的关键技巧。很多人第一次接触原地哈希时会感到困惑——既要使用哈希的思想来快速查找又不能分配额外空间这听起来像是矛盾的。但实际上原地哈希的核心思想非常巧妙利用数组本身作为哈希表通过元素交换和位置映射来实现 O(1) 空间复杂度的查找。本文将带你深入理解原地哈希的原理并通过 LeetCode 经典题目缺失的第一个正数第41题来掌握这一技巧的实际应用。1. 原地哈希要解决的核心问题1.1 传统哈希表的局限性在常规算法中当我们遇到需要快速查找元素是否存在的情况时第一反应通常是使用哈希表HashSet 或 HashMap。比如要找出数组中缺失的数字我们可以// 传统做法使用额外空间 public int findMissingNumber(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } for (int i 1; i nums.length; i) { if (!set.contains(i)) { return i; } } return -1; }这种方法的时间复杂度是 O(n)但空间复杂度也是 O(n)。在面试中面试官往往会追问能否在不使用额外空间的情况下解决1.2 原地哈希的适用场景原地哈希特别适用于以下类型的题目找出数组中缺失的最小正整数LeetCode 41找出数组中重复的数字LeetCode 287找出数组中消失的数字LeetCode 448第一个缺失的正数等变体问题这些题目的共同特点是数组长度已知元素范围有一定规律可以通过位置映射来记录信息。1.3 原地哈希的核心思想原地哈希的基本思路是让数组的索引与元素值建立对应关系。具体来说对于值为 x 的元素我们尝试将它放到数组中索引为 x-1 的位置上假设数组索引从 0 开始。通过这种物归原位的方式我们可以在遍历数组时通过检查nums[i]是否等于i1来判断数字是否存在。2. 原地哈希的基本原理与核心概念2.1 位置映射关系原地哈希最核心的概念就是建立元素值与数组索引的映射关系。对于大多数原地哈希问题我们使用以下映射规则元素值 x 应该位于数组索引 x-1 的位置这意味着数字 1 应该放在索引 0数字 2 应该放在索引 1数字 3 应该放在索引 2...数字 n 应该放在索引 n-12.2 交换策略为了实现上述映射我们需要遍历数组对于每个位置 i如果nums[i]的值在有效范围内通常是 1 到 n并且nums[i]不在它应该在的位置上那么就将nums[i]与它应该在的位置上的元素交换这个过程需要循环进行因为交换过来的新元素可能也需要继续交换。2.3 边界情况处理在实际实现中需要特别注意以下边界情况重复元素当存在重复数字时交换可能会陷入死循环超出范围的数字数字可能为负数、0或者大于数组长度原地交换要确保交换操作不会破坏已经就位的元素3. 环境准备与前置条件3.1 编程语言选择原地哈希算法与具体编程语言无关本文以 Java 为例进行演示但原理适用于所有主流编程语言。3.2 基础代码框架我们需要一个可以运行和测试的代码环境public class InPlaceHashing { public static void main(String[] args) { // 测试用例 int[] test1 {1, 2, 0}; int[] test2 {3, 4, -1, 1}; int[] test3 {7, 8, 9, 11, 12}; System.out.println(测试1结果: firstMissingPositive(test1)); // 应输出 3 System.out.println(测试2结果: firstMissingPositive(test2)); // 应输出 2 System.out.println(测试3结果: firstMissingPositive(test3)); // 应输出 1 } public static int firstMissingPositive(int[] nums) { // 原地哈希算法实现 // 具体实现见下文 } }3.3 理解题目要求以 LeetCode 41题缺失的第一个正数为例给定一个未排序的整数数组nums找出其中没有出现的最小的正整数时间复杂度必须是 O(n)空间复杂度必须是 O(1)示例输入[1,2,0]→ 输出3输入[3,4,-1,1]→ 输出2输入[7,8,9,11,12]→ 输出14. 原地哈希算法详细实现步骤4.1 第一步处理边界值和无效数字在开始交换之前我们需要先处理那些不在有效范围内的数字。对于寻找缺失正数的问题我们只关心 1 到 n 之间的数字n 是数组长度。// 第一步预处理 - 识别需要处理的数字范围 // 我们只关心数字 1 到 n其他数字可以忽略4.2 第二步实施原地交换这是算法的核心部分。我们遍历数组将每个数字放到它应该在的位置上。// 核心交换逻辑 int n nums.length; for (int i 0; i n; i) { // 当当前数字在有效范围内且不在正确位置上时进行交换 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { // 交换 nums[i] 和它应该在的位置上的元素 swap(nums, i, nums[i] - 1); } }4.3 第三步检查第一个不匹配的位置交换完成后我们再次遍历数组找到第一个nums[i] ! i 1的位置。// 检查第一个缺失的正数 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 如果所有位置都匹配说明缺失的是 n1 return n 1;4.4 完整的算法实现将上述步骤组合起来得到完整的原地哈希算法public class InPlaceHashing { // 交换数组中两个位置的元素 private static void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } public static int firstMissingPositive(int[] nums) { int n nums.length; // 第一步实施原地哈希 for (int i 0; i n; i) { // 只有当数字在 1 到 n 范围内且不在正确位置时才进行交换 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } // 第二步查找第一个不匹配的位置 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 如果所有位置都正确缺失的就是 n1 return n 1; } }5. 算法执行过程详细分析5.1 示例1[3, 4, -1, 1]的执行过程让我们逐步分析这个例子的执行过程初始数组[3, 4, -1, 1]第一次遍历i0nums[0] 3应该在索引 2 的位置当前索引 2 的值是 -1不相等进行交换交换后[-1, 4, 3, 1]继续 i0nums[0] -1不在 1-4 范围内跳过i1nums[1] 4应该在索引 3 的位置当前索引 3 的值是 1不相等进行交换交换后[-1, 1, 3, 4]继续 i1nums[1] 1应该在索引 0 的位置当前索引 0 的值是 -1不相等进行交换交换后[1, -1, 3, 4]i2nums[2] 3应该在索引 2 的位置已经在正确位置跳过i3nums[3] 4应该在索引 3 的位置已经在正确位置跳过最终数组[1, -1, 3, 4]检查结果索引 01 01 ✓索引 1-1 ≠ 11 → 第一个缺失的正数是 25.2 为什么使用 while 循环而不是 for 循环在核心交换部分我们使用while循环而不是简单的if判断这是因为// 错误的做法使用 if 判断 for (int i 0; i n; i) { if (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } // 问题交换后 nums[i] 位置的新元素可能也需要继续交换使用while循环确保每个位置上的元素都被正确处理直到它被放到正确位置或者是不需要处理的元素。6. 时间复杂度与空间复杂度分析6.1 时间复杂度分析虽然代码中有嵌套循环外层 for 循环内层 while 循环但总的时间复杂度仍然是 O(n)。这是因为每个元素最多被交换一次到正确位置一旦元素被放到正确位置就不会再被移动总共最多进行 n 次交换操作因此尽管有嵌套循环但总的操作次数是线性的。6.2 空间复杂度分析算法只使用了常数级别的额外空间几个临时变量没有使用任何与输入规模相关的额外数据结构因此空间复杂度是 O(1)。7. 常见问题与排查思路7.1 死循环问题问题现象程序陷入无限循环无法正常结束。可能原因存在重复元素时如果没有正确处理交换条件可能导致死循环。解决方案确保交换条件中包含nums[nums[i] - 1] ! nums[i]这个条件防止了将相同元素反复交换。// 正确的条件确保不会交换相同的元素 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); }7.2 数组越界问题问题现象出现ArrayIndexOutOfBoundsException。可能原因在计算nums[i] - 1时如果nums[i]是负数或0或者大于数组长度会导致索引越界。解决方案在访问数组前先检查索引的有效性。// 安全的做法先检查范围再访问 if (nums[i] 0 nums[i] n) { int targetIndex nums[i] - 1; if (nums[targetIndex] ! nums[i]) { swap(nums, i, targetIndex); } }7.3 结果错误问题问题现象可能原因排查方式解决方案总是返回1没有正确处理交换打印交换过程中的数组状态检查while循环条件是否正确返回n1但实际有缺失交换逻辑错误单步调试查看每个元素的最终位置验证映射关系是否正确对于特定测试用例失败边界情况未处理分析失败用例的特殊性增加对负数、0、大数的处理7.4 调试技巧当算法出现问题时可以添加调试输出来观察执行过程public static int firstMissingPositiveWithDebug(int[] nums) { int n nums.length; System.out.println(初始数组: Arrays.toString(nums)); for (int i 0; i n; i) { System.out.println(处理索引 i , 当前值: nums[i]); while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { System.out.println(交换 nums[i] 到索引 (nums[i] - 1)); swap(nums, i, nums[i] - 1); System.out.println(交换后数组: Arrays.toString(nums)); } } // ... 其余代码不变 }8. 原地哈希的变体与应用场景8.1 找出数组中重复的数字LeetCode 287题目要求给定一个包含 n 1 个整数的数组 nums其数字都在 1 到 n 之间包括 1 和 n可知至少存在一个重复的整数。假设只有一个重复的数字找出这个重复的数。原地哈希解法public int findDuplicate(int[] nums) { int n nums.length; for (int i 0; i n; i) { // 将数字放到对应的位置 while (nums[i] ! i 1) { if (nums[i] nums[nums[i] - 1]) { // 找到重复数字 return nums[i]; } swap(nums, i, nums[i] - 1); } } return -1; }8.2 找到所有数组中消失的数字LeetCode 448题目要求给定一个范围在 1 ≤ a[i] ≤ n ( n 数组大小 ) 的整型数组数组中的元素一些出现了两次另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。原地哈希解法public ListInteger findDisappearedNumbers(int[] nums) { int n nums.length; ListInteger result new ArrayList(); // 使用原地哈希将数字放到正确位置 for (int i 0; i n; i) { while (nums[i] ! i 1 nums[i] ! nums[nums[i] - 1]) { swap(nums, i, nums[i] - 1); } } // 遍历检查哪些位置上的数字不正确 for (int i 0; i n; i) { if (nums[i] ! i 1) { result.add(i 1); } } return result; }8.3 不同问题的对比分析问题类型核心思路特殊处理返回结果缺失的第一个正数将1-n的数字放到正确位置忽略超出范围的数字第一个不匹配的位置寻找重复数字交换过程中发现重复遇到重复立即返回重复的数字消失的数字同缺失第一个正数收集所有不匹配位置所有缺失数字的列表9. 最佳实践与工程建议9.1 代码可读性优化虽然原地哈希算法本身比较简洁但我们可以通过一些技巧提高代码的可读性public class InPlaceHashing { private static void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private static boolean shouldProcess(int num, int n) { return num 0 num n; } private static boolean isInCorrectPosition(int[] nums, int index) { return nums[index] index 1; } public static int firstMissingPositive(int[] nums) { int n nums.length; // 更清晰的逻辑表达 for (int i 0; i n; i) { while (shouldProcess(nums[i], n) !isInCorrectPosition(nums, nums[i] - 1)) { swap(nums, i, nums[i] - 1); } } for (int i 0; i n; i) { if (!isInCorrectPosition(nums, i)) { return i 1; } } return n 1; } }9.2 边界情况测试在实际项目中应该充分测试各种边界情况public class InPlaceHashingTest { Test public void testVariousCases() { // 正常情况 assertEquals(3, firstMissingPositive(new int[]{1, 2, 0})); assertEquals(2, firstMissingPositive(new int[]{3, 4, -1, 1})); assertEquals(1, firstMissingPositive(new int[]{7, 8, 9, 11, 12})); // 边界情况 assertEquals(1, firstMissingPositive(new int[]{})); // 空数组 assertEquals(2, firstMissingPositive(new int[]{1})); // 单元素 assertEquals(1, firstMissingPositive(new int[]{2})); // 单元素但缺失1 // 包含重复元素 assertEquals(3, firstMissingPositive(new int[]{1, 1, 2})); assertEquals(4, firstMissingPositive(new int[]{1, 2, 2, 3})); // 最大边界 assertEquals(6, firstMissingPositive(new int[]{1, 2, 3, 4, 5})); } }9.3 性能优化考虑虽然原地哈希已经是最优解但在实际应用中还可以考虑提前终止如果能在交换过程中提前发现结果可以提前返回内存局部性连续的数组访问有利于缓存命中避免不必要的交换仔细设计交换条件减少操作次数9.4 面试技巧在技术面试中讲解原地哈希时建议先讲暴力解法展示你理解问题的本质分析限制条件说明为什么需要 O(1) 空间复杂度逐步推导从简单例子开始演示算法思路处理边界情况展示你的代码健壮性分析复杂度证明算法满足要求原地哈希是算法面试中的高频考点掌握这一技巧不仅能解决特定问题更能体现你对空间复杂度的深刻理解和创造性解决问题的能力。通过本文的详细讲解和代码实践你应该能够 confidently 应对相关的算法挑战。建议将本文中的代码示例收藏备用在实际遇到相关问题时快速参考。对于想要进一步深入学习的读者可以尝试用原地哈希解决 LeetCode 上的相似题目如第268题缺失数字、第442题数组中重复的数据等巩固这一重要算法技巧。
原地哈希算法：O(1)空间复杂度解决数组查找问题
如果你正在准备算法面试或者刷过 LeetCode 的数组类题目很可能遇到过这样的场景题目要求找出数组中缺失的第一个正数或者找出重复的数字但附加条件往往是时间复杂度 O(n)空间复杂度 O(1)。这种限制意味着你不能使用额外的哈希表来存储元素也不能对数组进行排序排序通常需要 O(n log n) 时间。这时候原地哈希In-place Hashing就成为了解决问题的关键技巧。很多人第一次接触原地哈希时会感到困惑——既要使用哈希的思想来快速查找又不能分配额外空间这听起来像是矛盾的。但实际上原地哈希的核心思想非常巧妙利用数组本身作为哈希表通过元素交换和位置映射来实现 O(1) 空间复杂度的查找。本文将带你深入理解原地哈希的原理并通过 LeetCode 经典题目缺失的第一个正数第41题来掌握这一技巧的实际应用。1. 原地哈希要解决的核心问题1.1 传统哈希表的局限性在常规算法中当我们遇到需要快速查找元素是否存在的情况时第一反应通常是使用哈希表HashSet 或 HashMap。比如要找出数组中缺失的数字我们可以// 传统做法使用额外空间 public int findMissingNumber(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } for (int i 1; i nums.length; i) { if (!set.contains(i)) { return i; } } return -1; }这种方法的时间复杂度是 O(n)但空间复杂度也是 O(n)。在面试中面试官往往会追问能否在不使用额外空间的情况下解决1.2 原地哈希的适用场景原地哈希特别适用于以下类型的题目找出数组中缺失的最小正整数LeetCode 41找出数组中重复的数字LeetCode 287找出数组中消失的数字LeetCode 448第一个缺失的正数等变体问题这些题目的共同特点是数组长度已知元素范围有一定规律可以通过位置映射来记录信息。1.3 原地哈希的核心思想原地哈希的基本思路是让数组的索引与元素值建立对应关系。具体来说对于值为 x 的元素我们尝试将它放到数组中索引为 x-1 的位置上假设数组索引从 0 开始。通过这种物归原位的方式我们可以在遍历数组时通过检查nums[i]是否等于i1来判断数字是否存在。2. 原地哈希的基本原理与核心概念2.1 位置映射关系原地哈希最核心的概念就是建立元素值与数组索引的映射关系。对于大多数原地哈希问题我们使用以下映射规则元素值 x 应该位于数组索引 x-1 的位置这意味着数字 1 应该放在索引 0数字 2 应该放在索引 1数字 3 应该放在索引 2...数字 n 应该放在索引 n-12.2 交换策略为了实现上述映射我们需要遍历数组对于每个位置 i如果nums[i]的值在有效范围内通常是 1 到 n并且nums[i]不在它应该在的位置上那么就将nums[i]与它应该在的位置上的元素交换这个过程需要循环进行因为交换过来的新元素可能也需要继续交换。2.3 边界情况处理在实际实现中需要特别注意以下边界情况重复元素当存在重复数字时交换可能会陷入死循环超出范围的数字数字可能为负数、0或者大于数组长度原地交换要确保交换操作不会破坏已经就位的元素3. 环境准备与前置条件3.1 编程语言选择原地哈希算法与具体编程语言无关本文以 Java 为例进行演示但原理适用于所有主流编程语言。3.2 基础代码框架我们需要一个可以运行和测试的代码环境public class InPlaceHashing { public static void main(String[] args) { // 测试用例 int[] test1 {1, 2, 0}; int[] test2 {3, 4, -1, 1}; int[] test3 {7, 8, 9, 11, 12}; System.out.println(测试1结果: firstMissingPositive(test1)); // 应输出 3 System.out.println(测试2结果: firstMissingPositive(test2)); // 应输出 2 System.out.println(测试3结果: firstMissingPositive(test3)); // 应输出 1 } public static int firstMissingPositive(int[] nums) { // 原地哈希算法实现 // 具体实现见下文 } }3.3 理解题目要求以 LeetCode 41题缺失的第一个正数为例给定一个未排序的整数数组nums找出其中没有出现的最小的正整数时间复杂度必须是 O(n)空间复杂度必须是 O(1)示例输入[1,2,0]→ 输出3输入[3,4,-1,1]→ 输出2输入[7,8,9,11,12]→ 输出14. 原地哈希算法详细实现步骤4.1 第一步处理边界值和无效数字在开始交换之前我们需要先处理那些不在有效范围内的数字。对于寻找缺失正数的问题我们只关心 1 到 n 之间的数字n 是数组长度。// 第一步预处理 - 识别需要处理的数字范围 // 我们只关心数字 1 到 n其他数字可以忽略4.2 第二步实施原地交换这是算法的核心部分。我们遍历数组将每个数字放到它应该在的位置上。// 核心交换逻辑 int n nums.length; for (int i 0; i n; i) { // 当当前数字在有效范围内且不在正确位置上时进行交换 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { // 交换 nums[i] 和它应该在的位置上的元素 swap(nums, i, nums[i] - 1); } }4.3 第三步检查第一个不匹配的位置交换完成后我们再次遍历数组找到第一个nums[i] ! i 1的位置。// 检查第一个缺失的正数 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 如果所有位置都匹配说明缺失的是 n1 return n 1;4.4 完整的算法实现将上述步骤组合起来得到完整的原地哈希算法public class InPlaceHashing { // 交换数组中两个位置的元素 private static void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } public static int firstMissingPositive(int[] nums) { int n nums.length; // 第一步实施原地哈希 for (int i 0; i n; i) { // 只有当数字在 1 到 n 范围内且不在正确位置时才进行交换 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } // 第二步查找第一个不匹配的位置 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 如果所有位置都正确缺失的就是 n1 return n 1; } }5. 算法执行过程详细分析5.1 示例1[3, 4, -1, 1]的执行过程让我们逐步分析这个例子的执行过程初始数组[3, 4, -1, 1]第一次遍历i0nums[0] 3应该在索引 2 的位置当前索引 2 的值是 -1不相等进行交换交换后[-1, 4, 3, 1]继续 i0nums[0] -1不在 1-4 范围内跳过i1nums[1] 4应该在索引 3 的位置当前索引 3 的值是 1不相等进行交换交换后[-1, 1, 3, 4]继续 i1nums[1] 1应该在索引 0 的位置当前索引 0 的值是 -1不相等进行交换交换后[1, -1, 3, 4]i2nums[2] 3应该在索引 2 的位置已经在正确位置跳过i3nums[3] 4应该在索引 3 的位置已经在正确位置跳过最终数组[1, -1, 3, 4]检查结果索引 01 01 ✓索引 1-1 ≠ 11 → 第一个缺失的正数是 25.2 为什么使用 while 循环而不是 for 循环在核心交换部分我们使用while循环而不是简单的if判断这是因为// 错误的做法使用 if 判断 for (int i 0; i n; i) { if (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } // 问题交换后 nums[i] 位置的新元素可能也需要继续交换使用while循环确保每个位置上的元素都被正确处理直到它被放到正确位置或者是不需要处理的元素。6. 时间复杂度与空间复杂度分析6.1 时间复杂度分析虽然代码中有嵌套循环外层 for 循环内层 while 循环但总的时间复杂度仍然是 O(n)。这是因为每个元素最多被交换一次到正确位置一旦元素被放到正确位置就不会再被移动总共最多进行 n 次交换操作因此尽管有嵌套循环但总的操作次数是线性的。6.2 空间复杂度分析算法只使用了常数级别的额外空间几个临时变量没有使用任何与输入规模相关的额外数据结构因此空间复杂度是 O(1)。7. 常见问题与排查思路7.1 死循环问题问题现象程序陷入无限循环无法正常结束。可能原因存在重复元素时如果没有正确处理交换条件可能导致死循环。解决方案确保交换条件中包含nums[nums[i] - 1] ! nums[i]这个条件防止了将相同元素反复交换。// 正确的条件确保不会交换相同的元素 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); }7.2 数组越界问题问题现象出现ArrayIndexOutOfBoundsException。可能原因在计算nums[i] - 1时如果nums[i]是负数或0或者大于数组长度会导致索引越界。解决方案在访问数组前先检查索引的有效性。// 安全的做法先检查范围再访问 if (nums[i] 0 nums[i] n) { int targetIndex nums[i] - 1; if (nums[targetIndex] ! nums[i]) { swap(nums, i, targetIndex); } }7.3 结果错误问题问题现象可能原因排查方式解决方案总是返回1没有正确处理交换打印交换过程中的数组状态检查while循环条件是否正确返回n1但实际有缺失交换逻辑错误单步调试查看每个元素的最终位置验证映射关系是否正确对于特定测试用例失败边界情况未处理分析失败用例的特殊性增加对负数、0、大数的处理7.4 调试技巧当算法出现问题时可以添加调试输出来观察执行过程public static int firstMissingPositiveWithDebug(int[] nums) { int n nums.length; System.out.println(初始数组: Arrays.toString(nums)); for (int i 0; i n; i) { System.out.println(处理索引 i , 当前值: nums[i]); while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { System.out.println(交换 nums[i] 到索引 (nums[i] - 1)); swap(nums, i, nums[i] - 1); System.out.println(交换后数组: Arrays.toString(nums)); } } // ... 其余代码不变 }8. 原地哈希的变体与应用场景8.1 找出数组中重复的数字LeetCode 287题目要求给定一个包含 n 1 个整数的数组 nums其数字都在 1 到 n 之间包括 1 和 n可知至少存在一个重复的整数。假设只有一个重复的数字找出这个重复的数。原地哈希解法public int findDuplicate(int[] nums) { int n nums.length; for (int i 0; i n; i) { // 将数字放到对应的位置 while (nums[i] ! i 1) { if (nums[i] nums[nums[i] - 1]) { // 找到重复数字 return nums[i]; } swap(nums, i, nums[i] - 1); } } return -1; }8.2 找到所有数组中消失的数字LeetCode 448题目要求给定一个范围在 1 ≤ a[i] ≤ n ( n 数组大小 ) 的整型数组数组中的元素一些出现了两次另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。原地哈希解法public ListInteger findDisappearedNumbers(int[] nums) { int n nums.length; ListInteger result new ArrayList(); // 使用原地哈希将数字放到正确位置 for (int i 0; i n; i) { while (nums[i] ! i 1 nums[i] ! nums[nums[i] - 1]) { swap(nums, i, nums[i] - 1); } } // 遍历检查哪些位置上的数字不正确 for (int i 0; i n; i) { if (nums[i] ! i 1) { result.add(i 1); } } return result; }8.3 不同问题的对比分析问题类型核心思路特殊处理返回结果缺失的第一个正数将1-n的数字放到正确位置忽略超出范围的数字第一个不匹配的位置寻找重复数字交换过程中发现重复遇到重复立即返回重复的数字消失的数字同缺失第一个正数收集所有不匹配位置所有缺失数字的列表9. 最佳实践与工程建议9.1 代码可读性优化虽然原地哈希算法本身比较简洁但我们可以通过一些技巧提高代码的可读性public class InPlaceHashing { private static void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private static boolean shouldProcess(int num, int n) { return num 0 num n; } private static boolean isInCorrectPosition(int[] nums, int index) { return nums[index] index 1; } public static int firstMissingPositive(int[] nums) { int n nums.length; // 更清晰的逻辑表达 for (int i 0; i n; i) { while (shouldProcess(nums[i], n) !isInCorrectPosition(nums, nums[i] - 1)) { swap(nums, i, nums[i] - 1); } } for (int i 0; i n; i) { if (!isInCorrectPosition(nums, i)) { return i 1; } } return n 1; } }9.2 边界情况测试在实际项目中应该充分测试各种边界情况public class InPlaceHashingTest { Test public void testVariousCases() { // 正常情况 assertEquals(3, firstMissingPositive(new int[]{1, 2, 0})); assertEquals(2, firstMissingPositive(new int[]{3, 4, -1, 1})); assertEquals(1, firstMissingPositive(new int[]{7, 8, 9, 11, 12})); // 边界情况 assertEquals(1, firstMissingPositive(new int[]{})); // 空数组 assertEquals(2, firstMissingPositive(new int[]{1})); // 单元素 assertEquals(1, firstMissingPositive(new int[]{2})); // 单元素但缺失1 // 包含重复元素 assertEquals(3, firstMissingPositive(new int[]{1, 1, 2})); assertEquals(4, firstMissingPositive(new int[]{1, 2, 2, 3})); // 最大边界 assertEquals(6, firstMissingPositive(new int[]{1, 2, 3, 4, 5})); } }9.3 性能优化考虑虽然原地哈希已经是最优解但在实际应用中还可以考虑提前终止如果能在交换过程中提前发现结果可以提前返回内存局部性连续的数组访问有利于缓存命中避免不必要的交换仔细设计交换条件减少操作次数9.4 面试技巧在技术面试中讲解原地哈希时建议先讲暴力解法展示你理解问题的本质分析限制条件说明为什么需要 O(1) 空间复杂度逐步推导从简单例子开始演示算法思路处理边界情况展示你的代码健壮性分析复杂度证明算法满足要求原地哈希是算法面试中的高频考点掌握这一技巧不仅能解决特定问题更能体现你对空间复杂度的深刻理解和创造性解决问题的能力。通过本文的详细讲解和代码实践你应该能够 confidently 应对相关的算法挑战。建议将本文中的代码示例收藏备用在实际遇到相关问题时快速参考。对于想要进一步深入学习的读者可以尝试用原地哈希解决 LeetCode 上的相似题目如第268题缺失数字、第442题数组中重复的数据等巩固这一重要算法技巧。
