41. 缺失的第一个正数 - 力扣LeetCode为什么用哈希表哈希表是一个可以支持快速查找的数据结构给定一个元素我们可以在O(1)的时间查找该元素是否在哈希表中实现参考思路将数组所有的数放入哈希表随后从 1 开始依次枚举正整数并判断其是否在哈希表中。想清楚对于一个长度为 N 的数组其中没有出现的最小正整数只能在 [1,N1] 中。Ⅰ、筛选所以我们先把所有不可能是答案的负数、0、先筛去即放到答案范围之外即N1后面怎么筛0、负数一律变成N1第一轮筛选eg.1、0 、51、4、5for (int i 0; i n; i) { if (nums[i] 0) { nums[i] n 1; } }Ⅱ、标记符合要求的数字前面的那一个数字取为负数当作标记符号来用×原理解符合要求的数字前面那一个数字取负数标记 ❌实际原理拿当前读到的数字本身作为下标数字-1得到目标位置把这个目标位置的值标记成负数 ✅当作标记符号num ∈ [1,n]把nums[num-1]置负打标记表示 num 存在for (int i 0; i n; i) { int num Math.abs(nums[i]);//① 取绝对值防止已经被标记成负数 if (num n) { nums[num - 1] -Math.abs(nums[num - 1]);//② } }第二轮循环代码中两个取绝对值的位置分别有什么用①读数据时消除前面循环可能留下的负标记拿到原始数字②打标记时先消除目标位置已有的负号再强制置负避免重复数字反复翻转正负Ⅲ、根据标记找答案从左往右遍历数组找第一个 0 的位置下标 i答案就是 i1for (int i 0; i n; i) { if (nums[i] 0) { return i 1; } }这不是找到的第一个出现的正数本题目不是求第一个缺失的正数注意了这里找的是nums[i] 0而不是 0是没有标注的位置说明数字i1从来没有在数组里出现过否则即从第1个到第n个都不符合返回N1return n 1;完整代码回顾class Solution { public int firstMissingPositive(int[] nums) { int n nums.length; for (int i 0; i n; i) { if (nums[i] 0) { nums[i] n 1; } } for (int i 0; i n; i) { int num Math.abs(nums[i]); if (num n) { nums[num - 1] -Math.abs(nums[num - 1]); } } for (int i 0; i n; i) { if (nums[i] 0) { return i 1; } } return n 1; } }