题目 缺失的第一个正数

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

分析

思路1：哈希表，对于本题一个长度为N的数组，缺失的最小正整数为[1,N+1]之间，这是因为如果 [1,N] 都出现了，那么答案是 N+1。如何不使用额外的空间创建hash表呢？可以直接在原数组的基础上操作，首先将所有<=0的数变为数组长度+1，然后遍历数组，将所有出现过的元素对应索引处的位置添加负号作为标记，最后遍历数组找到数组内没有标记的元素即为缺失的最小正数或遍历完数组后为N+1

思路2：恢复元素在数组中的“正确位置”，数组应当有 [1, 2, ..., N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2

思路1代码：

public class Leetcode_41 {
    public static int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            //通过绝对值的方式防止标记的元素的影响
            int num = Math.abs(nums[i]);
            if (num <= len) { // 从0开始
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;

    }

    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums));
    }
}

思路2代码：

public static int firstMissingPositive(int[] nums) {
        int len = nums.length;
        //将元素置换到正确的位置
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len + 1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums));
    }