缺失的第一个正数

理解题目：

题目要求在未排序的整数数组中找到缺失的第一个正数。缺失的第一个正数指的是大于 0 并且不在数组中的最小正整数。

代码实现：

public class FirstMissingPositive {
    // 缺失的第一个正数
    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;
            }
        }

        // 标记出现过的正数
        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;
    }
}

步骤解释：

1. 将数组中所有非正数置为 n + 1，其中 n 是数组的长度。这样，所有不在 1 到 n 范围内的数都变为了 n + 1。

2. 遍历数组，对于每个出现过的正数 x，将索引为 x - 1 的位置的数置为负数，表示 x 已经出现过。

3. 再次遍历数组，找到第一个正数的索引，即为缺失的第一个正数。如果数组中没有正数，则缺失的第一个正数为 n + 1。

时间复杂度： 遍历数组三次，时间复杂度为 O(n)。

空间复杂度： 只使用了常数级别的额外空间，空间复杂度为 O(1)。