LeetCode：41. Missing first positive number

Here's an unsorted array of integers nums , Please find the smallest positive integer that doesn't appear in it .

Please implement a time complexity of O(n) And solutions that use only constant level extra space .

Example 1：

 Input ：nums = [1,2,0]
 Output ：3

Example 2：

 Input ：nums = [3,4,-1,1]
 Output ：2

Example 3：

 Input ：nums = [7,8,9,11,12]
 Output ：1

Tips ：

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

---

Their thinking

1. First of all, will nums[i] Put it in the right place , Such as nums[0] = 1,nums[1] = 2,…,nums[6] = 7
2. Then traverse the array after the exchange position , Determine whether it is the corresponding position , If it is not , Then directly return the current index value + 1; If it's all , Then return directly nums.length + 1 that will do

Code

/** * @param {number[]} nums * @return {number} */
var firstMissingPositive = function(nums) {
    
    for(let i = 0; i < nums.length; i++) {
    
      	//  loop nums, Current element in (0,nums.length] Between , also nums[nums[i]-1] != nums[i], Then switch places 
        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++) {
    //  Loop the array after swapping positions , Judge the first missing positive number 
        if(nums[i] != i+1) {
    
            return i+1;
        }
    }
	// [1,2,3]
    return nums.length + 1;
};