XingHuiSamaの宝藏之地

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

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

其实我先想到的是用哈希表，但是用哈希表开销太大了。

1. 算法核心思想

对于一个长度为 n 的数组，其缺失的最小正整数一定落在 1 到 n + 1 的范围内。因此，可以直接将原数组视作一个哈希表，通过交换操作，将属于范围 [1, n] 内的正整数放置到与其值对应的索引位置上（即数字 x 应该被放置在索引 x - 1 的位置）。重排完成后，再遍历检查第一个值与预期不符的位置，即可得出结果。

2. 执行逻辑梳理

遍历与重排： 使用第一个 for 循环遍历数组。当发现当前位置的数字没有“对号入座”（nums[i] != i + 1）时，尝试将其交换到正确的位置。
严格的条件过滤： 在执行交换的 while 循环中，包含三个利用 C++ “短路求值”特性的严格判断：
1. nums[i] > 0：排除负数和零，因为它们不属于正整数的讨论范围。
2. nums[i] <= nums.size()：排除大于数组长度的数字，这些数字超出了可能的答案区间。
3. nums[i] != nums[nums[i]-1]：验证目标位置上是否已经存在正确的数字。这一步不仅确保了交换的有效性，更排除了数组中存在重复元素时引发无限死循环的风险。
执行交换： 当满足上述三个条件时，将当前位置的数字与其目标位置的数字进行位置互换。while 循环会持续检查换回来的新数字，直到当前位置存放的是无法处理的数字或已归位的数字。
结果查找： 完成数组重排后，开启第二个 for 循环。从左向右检查，遇到的第一个不满足 nums[i] == i + 1 的索引 i，说明数字 i + 1 缺失，直接返回 i + 1。
边界情况处理： 如果第二个循环平稳结束，说明数组正好包含了从 1 到 n 的所有连续正整数。此时缺失的最小正整数即为数组长度加一，返回 nums.size() + 1。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i+1 ) {
                //交换
                while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i]-1]) {
                    int temp = nums[nums[i]-1];
                    nums[nums[i]-1] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return nums.size()+1;
    }
};

3. 复杂度分析

时间复杂度： O(n)。虽然代码中在 for 循环内部嵌套了 while 循环，但每一次成功的交换都会将一个数字永远固定在正确的位置上。整体来看，数组中的每个数字最多被访问和交换常数次，总操作次数与数组长度呈线性关系。
空间复杂度： O(1)。算法全程只利用了原数组的存储空间进行元素交换，仅使用了若干用于交换的临时整型变量，未开辟额外的数据结构，严格满足题目要求。