找到缺失的 第一个正数（算法题）

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

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

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例1：

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

示例2：

输入：nums = [3,4,-1,1]
输出：2

示例2：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

思路

如果本题没有额外的时空复杂度要求，那么就很容易实现：

我们可以将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中；

我们可以从 1 开始依次枚举正整数，并遍历数组，判断其是否在数组中。

如果数组的长度为 N，那么第一种做法的时间复杂度为O(N)，空间复杂度为 O(N)；第二种做法的时间复杂度为 O(N^2)，空间复杂度为 O(1)。但它们都不满足时间复杂度为 O(N)且空间复杂度为O(1)。

「真正」满足时间复杂度为 O(N) 且空间复杂度为O(1) 的算法是不存在的，但是我们可以退而求其次：利用给定数组中的空间来存储一些状态。也就是说，如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法；但如果我们可以修改给定的数组，那么是存在满足要求的算法的。

具体的解析，大家可以参考力扣41题。

public class Solution {

    public 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]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                // 例如：数值 3 应该放在索引 2 的位置上
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}