企业官网建设流程全解析

41. 缺失的第一个正数 - 力扣（LeetCode）

为什么用哈希表：

哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在O(1)的时间查找该元素是否在哈希表中

实现参考思路：

将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中。

想清楚：对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。

Ⅰ、筛选

所以我们先把所有不可能是答案的：负数、0、先筛去（即放到答案范围之外，即N+1后面）

怎么筛？

0、负数一律变成N+1（第一轮筛选）eg.1、0 、5=>1、4、5

for (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，答案就是 i+1

for (int i = 0; i < n; ++i) { if (nums[i] > 0) { return i + 1; } }

这不是找到的第一个出现的正数？本题目不是求第一个缺失的正数？

注意了这里找的是nums[i]> 0而不是< 0，是没有标注的位置，说明数字i+1从来没有在数组里出现过

return 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; } }