缺失的第一个正数：原地哈希与标记法详解

方法二：符号标记法（官方推荐）

这种方法逻辑更简洁，避免了交换操作的边界问题。核心思想是利用数组元素的正负号来标记「1~n 范围内的数是否出现过」。正数表示未出现，负数表示已出现。

关键步骤拆解

1. 预处理非正整数：将所有非正整数（≤0）替换为 n+1。这些数对结果无影响，统一标记为'无效值'，避免干扰后续的正负号判断。
2. 标记出现状态：再次遍历数组，取绝对值 num = Math.abs(nums[i])。如果 num 在 1~n 范围内，就将索引 num-1 处的数标记为负数。这里必须用 -Math.abs(...)，防止重复标记导致符号反转（例如数组有重复数时）。
3. 查找结果：遍历数组，找到第一个仍为正数的索引 i，返回 i+1。如果全为负数，说明 1~n 都存在，返回 n+1。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // 步骤 1：将所有非正整数替换为 n+1
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        
        // 步骤 2：用'正负号'标记 1~n 范围内的数是否出现过
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                // 将 num 对应的索引位置的数标记为负数
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        
        // 步骤 3：找到第一个正数的索引，返回索引 +1
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        // 如果数组全为负数，返回 n+1
        return n + 1;
    }
}

示例验证

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

最终结果为 2，符合预期。

复杂度分析

• 时间复杂度：O(n)。每个元素最多被访问常数次，三次线性遍历。
• 空间复杂度：O(1)。仅使用常数额外空间，原地修改数组。

这种'标记法'是原地哈希的经典应用，相比置换法，逻辑更简洁且避免了交换操作的边界问题，是这道题的最优解法之一。