空间复杂度为1的算法，将数组本身当做哈希空间

将出现过的正数位置标记出来两种方法：1、用正负标记。2、将合法数字交换到对应的位置，不对应的即为第一个缺失的数字。

class Solution41 {
    // 1、将为负数的位置变为正数，可以用n+1
    // 2、nums[i]<=n 情况下 将num[i]-1位置数字变为负数，标记位该位置数字已经出现过了
    // 3、遍历数组 第一个非负数字位置+1 即是未出现过的最小正数
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 负数全变成正数
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        // 小于n的正数对应位置变成负数表示该数字已经出现过了
        for (int i = 0; i < n; i++) {
            // i位置可能已经被更改
            int x = Math.abs(nums[i]);
            if (x <= n) {
                nums[x - 1] = -Math.abs(nums[x - 1]);
            }
        }

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

class Solution41_swap {
    // 1、将 num[i] 放到 num[i]-1 位置，即将 i和num[i] 位置数字互换，直到不合法。
    //      注意循环条件 当num[i] == num[num[i]-1] 时，会陷入无限循环，此时应打断。
    // 2、判断 遍历判断 num[i]-1 == i 如果不相等，则该位置上数字没有出现过
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }

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

    private void swap(int[] nums, int s1, int s2) {
        int temp = nums[s1];
        nums[s1] = nums[s2];
        nums[s2] = temp;
    }
}