LeetCode 41 缺失的第一个正数：原地哈希两种思路

这种方法逻辑直观，但交换的边界条件容易出错，代码写起来要小心。

解法二：正负号标记

置换法的 while 比较绕，官方给出的标记法更简洁。它不交换元素，而是通过改变正负号来记录信息。

步骤拆解：

1. 遍历数组，把所有 ≤0 的数替换成 n+1。这些数对结果没贡献，替换成一个超出范围的数后可以安全忽略。
2. 再次遍历，对每个数取绝对值 num = abs(nums[i])，如果 num 在 [1, n] 内，就把 nums[num-1] 置为负数，表示数字 num 出现过。这里要用 -abs(nums[num-1]) 而不是简单地取负，因为某个数字可能多次出现，这样可以避免负负得正导致标记丢失。
3. 最后遍历，第一个正数对应的索引 i+1 就是答案。如果全部都是负数，说明 1~n 都出现了，返回 n+1。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 把非正整数替换成 n+1
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        // 用正负号标记 1~n 是否出现
        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;
    }
}

用同样的例子 [3,4,-1,1]（n=4）跑一遍：

• 第一步：将 ≤0 的元素 -1 替换成 5，数组变成 [3,4,5,1]。
• 第二步：i=0，num=3，标记 nums[2] 为 -5 → [3,4,-5,1]；i=1，num=4，标记 nums[3] 为 -1 → [3,4,-5,-1]；i=2，num=5 > 4，跳过；i=3，num=1，标记 nums[0] 为 -3 → [-3,4,-5,-1]。
• 第三步：扫描，索引 1 的 4 是正数，返回 2。

[1,2,0]（n=3）的过程也类似，最终在索引 2 找到正数 4，返回 3。

标记法全程只依赖取绝对值和取负，没有交换，代码简洁得多。这也是官方题解采用的方法。

复杂度

两种解法都是三次线性遍历（置换法的每次 while 交换均摊 O(1)），时间 O(n)，空间 O(1)，完全符合题目要求。

实际刷题时，标记法更容易一次写对。不过两种思路都值得了解——用数组自身做哈希的思想在很多限制空间的题目里都用得上。