41. The first missing positive number

One 、 Title Description

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

Two 、 Problem solving

The array is treated as a hash table （ In situ hash ）

take [1,n] Put the elements in i-1 The subscript , Exchange two values , Guarantee num[i] stay i-1 The subscript , If it doesn't exist , Just put it in that position [1,n] Between .

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        // take [1,n] Put the elements in i-1 The subscript  , Exchange two values 
        int length = nums.length;
        for(int i = 0;i<length;i++){
    
            // Guarantee num[i] stay i-1 The subscript , If it doesn't exist , Just put it in that position  [1,n] Between 
            while(nums[i] > 0 && nums[i] <= length && nums[nums[i]-1] != nums[i]){
    
                swap(nums,i,nums[i]-1);
            }
        }
        // Traversal array 
        for(int i = 0;i<length;i++){
    
            if(nums[i] != i+1){
    
                return i+1;
            }
        }
        return length+1;

    }
    public void swap(int[] nums,int left,int right){
    
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}