缺失的第一个正数

41. 缺失的第一个正数

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

示例 1:

1 2	输入: [1,2,0] 输出: 3

示例 2:

1 2	输入: [3,4,-1,1] 输出: 2

示例 3:

1 2	输入: [7,8,9,11,12] 输出: 1

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

如果没有时空复杂度要求可以很容易实现：

将数组所有数放入哈希表，从 1 开始枚举正整数，并判断其是否在哈希表中。
将从 1 开始枚举正整数，遍历数组判断其是否存在。

第一种方法时间复杂度O(n)，空间复杂度O(n)；第二种方法时间复杂度O(n^2)，空间复杂度O(1)。

此题要求时间复杂度O(n)，空间复杂度O(1)。如果题目给的数组是不可修改的，那么不存在满足要求的算法，如果我们可以修改给定的数组，那么可以做到满足要求的算法。

方法一：哈希表

我们可以将给定数组当作哈希表。对于一个长度为 N 的数组来说，没有出现的最小正整数只能在[1, N + 1] 中出现。如果[1, N]都出现，那么答案为 N + 1，否则答案是 [1, N] 中没有出现的最小正整数。这样一来，我们将所有在 [1, N] 中的数放入哈希表，正好数组的长度为 N ，我们可以将其设计为哈希表：

遍历数组，对于遍历到的数 x ，如果 x ∈ [1, N]，将数组中第 x - 1 个位置（下标从 0 开始）上的数变为负数。在遍历结束后，如果所有位置都为负数，那么答案是 N + 1，否则答案是正数的位置加 1 。

对于数组中的负数我们首先将其变为 N + 1 ，然后遍历数组将[1, N] 中出现的数字对应的位置上的数字变为负数，再次遍历数组，数组中数字为正数的位置加 1 即为结果，全为负数则结果为 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;
            }
        }
		//上标记
        for(int i = 0; i < n; i++){
            //数组中数字可以为负数，应对其取绝对值
            int x = Math.abs(nums[i]);
            if(x < n + 1){
                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;
    }
}

时间复杂度O(n)，空间复杂度O(1)。

方法二：置换

与方法一类似，将数组当作哈希表，我们将下标为x - 1 的位置放数字 x。我们对数组进行一次遍历，如果遍历到的数字 x = nums[i] 且 x ∈ [1, N] ，我们直到 x 应该放置在 x - 1 位置上，那么我们交换 nums[i] 和 nums[x - 1]，这样 x 就出现在了正确的位置，注意当 nums[i] == nums[x - 1] 时应该直接进行下次遍历，不再交换。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            while(nums[i] > 0 && nums[i] <= n && 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 < n; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return n + 1;
    }
}

时间复杂度O(n)，最多进行 n 次交换。空间复杂度O(1)。