题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：
输入：nums = [1,2,0]
输出：3

思路 - O(n)空间

对于长度为n的数组nums来说，缺失的正整数要么在 [1, N] 中，要么是 N+1。可以用一个变量从1开始每次增量，并检查变量是否在nums中。
检查nums是否存在变量可以用哈希表。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) { // 构建哈希表
            set.add(n);
        }
        int res = 1;
        for ( ; res <= nums.length; res++) {  // res = [1,N]
            if (!set.contains(res)) {
                return res;
            }
        }
        return res;
    }
}

思路 - O(1)空间

把nums数组本身当做哈希表来用，妙到家了。

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;
            }
        }
        // 标记正整数在nums中应该在的位置。怎么标记？用负号。
        for (int i = 0; i < n; i++) {
            int value = Math.abs(nums[i]);
            if (value <= n) {
                nums[value - 1] = -Math.abs(nums[value - 1]);
            }
        }
        // 如果这个位置没被标记过说明缺失的是这个数。
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        // 如果都被标记过说明缺失的是 n+1
        return n + 1;
    }
}