题目

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

要求：

• 时间复杂度必须为 O(n)
• 只能使用常数级别的额外空间（即 O(1) 额外空间）

---

示例 1

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

输出：
3

解释：
数字 1 和 2 已经存在，最小缺失的正整数是 3。

---

示例 2

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

输出：
2

解释：
数字 1 存在，但 2 不存在，因此最小缺失的正整数是 2。

---

示例 3

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

输出：
1

解释：
最小的正整数 1 不在数组中。

---

提示

• 1 <= nums.length <= 10^5
• -2^{31} <= nums[i] <= 2^{31} - 1

实现

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 当遇到每一个数 把它放在应该在的位置上
        // 1 -> index 0 依次类推
        for(int i = 0 ; i < nums.size() ; ) {
            // 如果数字不在范围或者已经呆在正确位置,则不处理
            if (nums[i] <= 0 || nums[i] > nums.size() || nums[i] == i + 1) {
                i ++;
                continue;
            }
            // 长度为 n 的数组中缺省的最大正整数为 n + 1 所以 大于 n 的数组不用处理
            int target = nums[i] - 1;
            // 如果这个位置已经有一个正确防止的元素, 那么不处理这个数字, 并且腾出该数字的位置
            if (nums[target] == target + 1) {
                nums[i] = -1; // 腾出该数字的位置 这样后续遇到该数字不会处理
                i ++;
                continue;
            }
            swap(nums[target] , nums[i]); // 将这个数字放到应该的位置上

        }
        for(int i = 0 ; i < nums.size() ; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        // 如果前面没有放回 说明 1 - n 都存在
        return nums.size() + 1;
    }
};