[41]缺失的第一个正数

//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 
//
// 
//
// 进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？ 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,0]
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,4,-1,1]
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：nums = [7,8,9,11,12]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 300 
// -231 <= nums[i] <= 231 - 1 
// 
// Related Topics 数组 
// 👍 976 👎 0

/*
* 41 缺失的第一个正数
* 2021-03-04 12:17:27
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        // result must be in [1...n]
        // if(the node k belong to [1..n], then places it at position k - 1
        for(int i = 0;i < n;i++){
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);
        }

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

    }
};
//leetcode submit region end(Prohibit modification and deletion)