LeetCode41——First Missing Positive——hashing in place ＆ swap

This problem lets us find the missing first element in an array , That is to say The smallest positive number , The questions are as follows ：

In fact, it is not difficult to realize this function , The difficulty lies in the problem of the algorithm Time and space complexity make constraints at the same time , That is, the complexity of time is $O(n)$, At the same time, the spatial complexity is $O(1)$.

Before finishing this problem , One very important observation is ：
For length is N Array of nums, The minimum missing positive number will only be in the interval $[1,N+1]$ Inside , in other words , The length is N The array of will only occupy $[1,N]$ this N A positive integer , So that the first missing positive integer is N+1. Other special cases include the presence of greater than in the array N The positive integer , Or non positive integer (<=0 Number of numbers ), Will make the smallest missing positive integer fall in $[1,N]$ In this range , This conclusion is the premise to complete this problem .

Time complexity and space complexity are both $O(n)$ The algorithm of can be Apply for a length of n Array of Flag Express $[1,N]$, For convenience, I take one more element here , Then mark one by one in nums The elements that appear in , Then look at the first positive number that doesn't appear . The code is as follows ：

int firstMissingPositive(vector<int>& nums) {
    
        /*O(n)-O(n) algorithm*/
        /*apply for a flag array to record existing element*/
        bool* Flag = new bool [nums.size() + 1];
        for(int i = 0 ; i <= nums.size() ; ++i)
            Flag[i] = false;
		
		/*set flag[nums[i]] as true when nums[i]∈[1, N]*/
        size_t Size = nums.size();
        int Result = Size + 1;
        for(int i = 0 ; i < nums.size() ; ++i)
            if(nums[i] > 0 && nums[i] <= Size)
                Flag[nums[i]] = true;
                
		/*search for the first missing positive number*/
        for(int i = 1 ; i <= nums.size() ; ++i)
            if(!Flag[i])
            {
    
                Result = i;
                break;
            }
               
        delete [] Flag;    
        return Result;
    }

This simple way increases the spatial complexity , Reduced time complexity , Just traverse 2 The number group is ok . However, it still fails to meet the requirements of the topic while taking into account the time complexity and space complexity , Here you are The two methods To achieve this goal （ Learned from the official explanation , cry :(：

One 、 In place hash (hashing in place)
This way is mainly in the original nums Array $[1,N]$ The tag , This algorithm is divided into the following steps ：

• Traverse nums for the first time , Will the Less than or equal to 0 All elements of are modified to N+1,N It's array length . This is because Later, you need to subtract... From the elements in the array 1 Mark as a subscript nums The elements in . Negative numbers and 0 subtract 1 Then the index value will become negative . Modified into N+1 Then it will eliminate this problem , and N+1-1 = N, It will not be marked nums Any element in (nums The maximum available index is N-1).
• Traverse nums The second time , take nums Array Between the range $[1,N]$ Subtract 1 As a subscript , Set the element corresponding to the subscript to a negative number to indicate that this element exists .
• Traverse nums third time , Look at the first positive integer that appears in nums Which one of them , Let's say the number one in the array is i Bits are positive , that Indicates the positive number corresponding to this index i+1 Never had . Assume negative numbers , So the first positive number that doesn't appear is N+1.

The following is the source code of the implementation ：

int firstMissingPositive(vector<int>& nums) {
    
        int Size = nums.size();
		
		/*Iteration 1*/
        for(int i = 0 ; i < Size ; ++i)
            if(nums[i] <= 0)    
                nums[i] = Size + 1;
        
        /*Iteration 2*/
        for(int i = 0 ; i < Size ; ++i)
        {
    
            int num = abs(nums[i]);	// num must be larger than 0
            if(num <= Size)			// make sure the num is less than N
                nums[num - 1] = -abs(nums[num - 1]);	// make sure the value is negative
        }
                
        /*Iteration 3*/
        for(int i = 0 ; i < Size ; ++i)
            if(nums[i] > 0)
                return i + 1;
        
        return Size + 1;
    }

Two 、 Local exchange (swap)
This algorithm is simpler than local hash , Its core idea is to put every element into it “ belong ” The location of . say concretely , One is worth $x\in [1,N]$ The elements of , It should be indexed x-1 The location of , We just need Swap it with the element where it should be that will do .

But note that this exchange is not It was done in one stroke , The newly replaced element also needs to be arranged in the position it should be , So this is a The logic of the cycle . Finally, there is a special case that needs to be discussed , That's it If the two elements exchanged are the same , You're going to fall into a dead circle ( The two elements are constantly changing ), Therefore, the discussion and avoidance of this situation should be added to the conditions of circulation .

One last check nums Array , The first element that appears where it should not appear Is the smallest positive number missing .
The overall code is as follows ：

int firstMissingPositive(vector<int>& nums) {
    
        int Size = nums.size();
        for(int i = 0 ; i < Size ; ++i)
        {
    
        /*2 conditions:*/
        /*1.nums[i] ∈ [1,N]*/
        /*2.avoid infinite loop*/
            while(nums[i] > 0 && nums[i] <= Size && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        }

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