目录一、什么是原地 Hash1. 核心概念2. 适用场景3. 核心思想二、方案 1正负标记法最常用原理适用题型Java 完整实现1. 查找数组中重复的数字2. 查找 1~n 中缺失的数字优缺点正负标记法三、方案 2交换归位法循环置换原地 Hash原理Java 完整实现1. 基础版归位 找重复 / 缺失2. 进阶LeetCode 41 题 —— 缺失的第一个正数经典原地 Hash优缺点交换归位法四、两种原地 Hash 对比总结五、关键注意点踩坑提醒一、什么是原地 Hash1. 核心概念原地 Hash也叫数组原地哈希、就地哈希是一种不额外开辟大内存空间直接利用原数组下标作为哈希映射地址在原数组上完成哈希标记、查找、去重、找缺失数、找重复数等问题的算法。常规哈希新建HashSet/HashMap存数据空间复杂度 O(n) 原地哈希仅使用常数级额外空间 O(1)时间复杂度通常 O(n)属于空间换时间的反向优化。2. 适用场景前提条件必须满足 数组元素满足元素值的范围和数组下标范围强绑定常见两类场景数组长度为 n元素范围[1,n]最经典找重复数、缺失数数组长度为 n元素范围[0,n−1]典型题目寻找数组中重复的数字寻找 1∼n 中缺失的数字数组中第一个缺失的正数数组元素原地去重限定值域3. 核心思想利用数组下标 哈希 key数组值 哈希存在标记遍历数组把每个元素num映射到下标idx num - 1适配 [1,n] 值域原地标记该下标位置表示「这个数字已经出现过」常用标记方式取负数不破坏原始数值后续可还原交换归位把数字放到「它本该在的下标位置」排序 哈希二合一遍历完成后根据标记结果判断重复 / 缺失。两种主流原地 Hash 方案正负标记法简单适合查重复 / 缺失不改变数组顺序交换归位法循环交换把数字放到对应下标功能更强二、方案 1正负标记法最常用原理数组元素值域 [1,n]下标 [0,n−1]数字x对应的目标下标x - 1每遇到一个x将nums[x-1]取反标记已出现规则遍历每个元素取绝对值作为当前数字防止已被取负若目标下标位置已是负数→ 该数字重复遍历结束后仍为正数的下标 1→ 就是缺失的数字适用题型找出数组中所有重复数字找出 1∼n 中缺失的数字Java 完整实现1. 查找数组中重复的数字import java.util.ArrayList; import java.util.List; /** * 原地Hash - 正负标记法查找重复数字 * 条件数组长度 n元素范围 [1, n] * 空间复杂度 O(1)时间复杂度 O(n) */ public class InPlaceHashNegative { public static ListInteger findDuplicates(int[] nums) { ListInteger res new ArrayList(); int n nums.length; for (int i 0; i n; i) { // 取绝对值当前实际数字 int cur Math.abs(nums[i]); // 数字 cur 对应下标 cur - 1 int idx cur - 1; if (nums[idx] 0) { // 该位置已被标记说明 cur 重复出现 res.add(cur); } else { // 原地标记取反 nums[idx] -nums[idx]; } } return res; } public static void main(String[] args) { int[] arr1 {4, 3, 2, 7, 8, 2, 3, 1}; ListInteger duplicates findDuplicates(arr1); System.out.println(重复数字 duplicates); // [2, 3] int[] arr2 {1, 1, 2}; System.out.println(重复数字 findDuplicates(arr2)); // [1] } }2. 查找 1~n 中缺失的数字基于同样标记逻辑最后遍历数组正数下标 1 即为缺失值/** * 原地Hash - 查找 1~n 缺失的数字 */ public class FindMissingNumber { public static int findMissing(int[] nums) { int n nums.length; // 第一步正负标记 for (int i 0; i n; i) { int cur Math.abs(nums[i]); int idx cur - 1; nums[idx] -Math.abs(nums[idx]); } // 第二步找到正数位置下标1 就是缺失数 for (int i 0; i n; i) { if (nums[i] 0) { return i 1; } } // 全部都存在缺失 n1边界 return n 1; } public static void main(String[] args) { int[] arr1 {3, 1, 3, 4, 2}; System.out.println(缺失数字 findMissing(arr1)); // 5 int[] arr2 {1, 2, 4}; System.out.println(缺失数字 findMissing(arr2)); // 3 } }优缺点正负标记法✅ 优点逻辑简单、代码短不会打乱原数组元素相对顺序严格 O(1) 原地空间❌ 缺点仅适用于正数值域 [1,n]无法处理 0、负数、超出 [1,n] 的元素三、方案 2交换归位法循环置换原地 Hash原理核心让每个数字x归位到下标x-1的位置形成「下标 数字 - 1」的有序映射。流程遍历数组i期望nums[i] i 1数字归位如果当前数字nums[i]不在正确位置循环交换把nums[i]交换到它对应的下标idx nums[i] - 1直到nums[i]合法 / 遇到重复元素判断规则交换时若nums[cur-1] cur→重复数字最终nums[i] ! i1的位置 →缺失数字该方法兼容性更强是面试高频考点经典题第一个缺失的正数必用此方案。Java 完整实现1. 基础版归位 找重复 / 缺失/** * 原地Hash - 交换归位法循环置换 * 适用元素 [1,n]找重复、缺失数 */ public class InPlaceHashSwap { // 查找重复数字 public static int findDuplicate(int[] nums) { int n nums.length; for (int i 0; i n; i) { // 当前数字不在正确位置持续交换归位 while (nums[i] ! i 1) { int cur nums[i]; int idx cur - 1; // 目标位置已经是 cur → 重复 if (nums[idx] cur) { return cur; } // 原地交换 swap(nums, i, idx); } } return -1; } // 查找 1~n 缺失的数字 public static int findMissing(int[] nums) { int n nums.length; // 第一步全部归位 for (int i 0; i n; i) { while (nums[i] 1 nums[i] n nums[i] ! i 1) { int cur nums[i]; int idx cur - 1; if (nums[idx] cur) break; // 重复跳出 swap(nums, i, idx); } } // 第二步遍历找位置不对的下标 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1; } // 原地交换数组两个位置 private static void swap(int[] nums, int a, int b) { int temp nums[a]; nums[a] nums[b]; nums[b] temp; } public static void main(String[] args) { int[] arr1 {2, 3, 1, 2}; System.out.println(重复数字 findDuplicate(arr1)); // 2 int[] arr2 {1, 3, 4, 5}; System.out.println(缺失数字 findMissing(arr2)); // 2 } }2. 进阶LeetCode 41 题 —— 缺失的第一个正数经典原地 Hash题目给定无序数组找出最小的正整数要求 O(n) 时间、O(1) 空间。 数组可包含负数、0、大于数组长度的数只能用交换归位原地 Hash解决。public class FirstMissingPositive { public static int firstMissingPositive(int[] nums) { int n nums.length; // 原地归位只处理 [1, n] 之间的正数 for (int i 0; i n; i) { // 三个条件是正整数、在数组范围内、不在正确下标 while (nums[i] 1 nums[i] n nums[nums[i] - 1] ! nums[i]) { int idx nums[i] - 1; swap(nums, i, idx); } } // 遍历第一个不满足 nums[i] i1 的就是答案 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 1~n 全部存在答案是 n1 return n 1; } private static void swap(int[] nums, int a, int b) { int t nums[a]; nums[a] nums[b]; nums[b] t; } public static void main(String[] args) { int[] arr1 {1, 2, 0}; System.out.println(firstMissingPositive(arr1)); // 3 int[] arr2 {3, 4, -1, 1}; System.out.println(firstMissingPositive(arr2)); // 2 int[] arr3 {7, 8, 9, 11, 12}; System.out.println(firstMissingPositive(arr3)); // 1 } }优缺点交换归位法✅ 优点适用范围广可处理负数、0、超大值功能最强能解决「最小缺失正数」等高难度题纯原地操作O(1) 空间❌ 缺点会打乱原数组顺序循环交换逻辑比正负标记稍复杂四、两种原地 Hash 对比总结方案空间时间值域限制数组顺序适用场景正负标记法O(1)O(n)仅 [1,n] 正数不改变找重复、找缺失简单题交换归位法O(1)O(n)无强限制打乱最小缺失正数、复杂值域场景面试必考五、关键注意点踩坑提醒值域绑定是前提原地 Hash 本质是「下标映射」元素必须和下标范围对应否则无法使用正负标记法中一定要取绝对值避免已被取反的数字计算出错交换归位必须加while循环不能只用if因为交换后当前位置新元素仍可能需要归位边界处理当 1∼n 全部存在时缺失值为 n1。