当前位置：首页 > news >正文

力扣hot100:缺失的第一个正数（哈希思想）（41）

news 2025/9/3 21:34:46

题目描述：

解题思路

核心思路是通过原地标记实现空间复杂度 O(1)。缺失的最小正整数一定在 [1, n+1] 范围内（n 是数组长度），因此只需关注这个范围内的数。分三步操作：

预处理非正数：将所有非正数（负数和零）替换为 n+1，避免干扰后续标记。
标记出现过的数：遍历数组，对每个值 x，若 x ∈ [1, n]，将位置 x-1 的值标记为负数（表示 x 出现过）。
查找缺失数：再次遍历数组，第一个正数所在位置 i 表示 i+1 是缺失的最小正整数；若全为负数，则缺失的是 n+1。

代码实现

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;// 步骤1：将所有非正数替换为 n+1for (int i = 0; i < n; i++) {if (nums[i] <= 0) {nums[i] = n + 1;}}// 步骤2：标记出现过的数for (int i = 0; i < n; i++) {int num = Math.abs(nums[i]); // 取绝对值（可能已被标记为负）if (num <= n) {// 将 num-1 位置的值置为负数（表示 num 出现过）nums[num - 1] = -Math.abs(nums[num - 1]); }}// 步骤3：查找第一个正数位置for (int i = 0; i < n; i++) {if (nums[i] > 0) {return i + 1; // 当前位置未标记，i+1 即为缺失的数}}return n + 1; // 所有位置均被标记，缺失 n+1}
}

关键步骤解析

预处理非正数：

   for (int i = 0; i < n; i++) {if (nums[i] <= 0) {nums[i] = n + 1; // 替换为超出范围的值}}

非正数不影响结果，替换为 n+1 后，数组中只剩正数，便于后续标记。

负数标记法：

   int num = Math.abs(nums[i]); // 获取原始值（可能已被其他操作标记为负）if (num <= n) {nums[num - 1] = -Math.abs(nums[num - 1]); // 确保标记为负数}

绝对值的作用：若 nums[i] 已被标记为负，Math.abs 能还原其原始值。
负号标记：通过将 nums[num-1] 设为负数，表示 num 出现过（如 num=3 则标记索引 2）。
避免重复标记：Math.abs(...) 确保即使位置已被标记，也不会因二次取负变正。

查找缺失数：

   for (int i = 0; i < n; i++) {if (nums[i] > 0) {return i + 1; // 位置 i 未标记，说明 i+1 缺失}}return n + 1;

若位置 i 的值为正，说明 i+1 未出现过（未被标记）。

复杂度分析

时间复杂度：三次遍历，总计 O(n)。
空间复杂度：O(1)，仅用常量空间。

示例推演

以 nums = [3, 4, -1, 1] 为例：

预处理：替换非正数 -1 → 5，数组变为 [3, 4, 5, 1]。
标记出现过的数：
- 3 → 标记索引 2：[3, 4, -5, 1]
- 4 → 标记索引 3：[3, 4, -5, -1]
- 5 → 跳过（超出范围）
- 1 → 标记索引 0：[-3, 4, -5, -1]
查找缺失数：索引 1 的值为正数 4 → 缺失数 1+1=2。