LeetCode：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

提示：

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

---

解题思路

1.首先将nums[i]放到对应的位置，如nums[0] = 1，nums[1] = 2，…，nums[6] = 7
2.然后遍历交换位置之后的数组，判断是否是对应位置，若不是，则直接返回当前索引值 + 1；若全都是，则直接返回nums.length + 1即可

代码

/** * @param {number[]} nums * @return {number} */
var firstMissingPositive = function(nums) {
    
    for(let i = 0; i < nums.length; i++) {
    
      	// 循环nums，当前元素在(0,nums.length]之间，并且nums[nums[i]-1] != nums[i]，则交换位置
        while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]) {
    
            const temp = nums[nums[i]-1];
            nums[nums[i]-1] = nums[i];
            nums[i] = temp;
        }
    }
    for(let i = 0; i < nums.length; i++) {
    // 循环交换位置之后的数组，判断第一个缺失的正数
        if(nums[i] != i+1) {
    
            return i+1;
        }
    }
	// [1,2,3]
    return nums.length + 1;
};