41. First Missing Positive Leetcode Java

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:

Actually the first solution came to my mind is sort the array and check the first missing positive element, however, the time complexity is not O(n). Or we can use another array with the same size to store the number from original array, where helper[index]=index, then we search the helper array, when we find the first occurrence of helper[index]!=index, which is the first missing positive number. However it is still not meet the requirement of use constant space.

Then why don't we use the original array, to do the job of the helper array.

During the transverse of the array, when A[index]!= index, if A[index] is a valid index of A, then swap A[index] with A[A[index]]. After this operation, valid index number will be in its index position, so the first one that mismatch occurred will be the first missing positive number.
Time complexity: O(n) with constant space.

 public int firstMissingPositive(int[] A) {  
     if(A==null || A.length==0) return 1;  
     for(int i=0;i<A.length;i++){  
       int num=A[i];  
       if(num>0 && num<=A.length && A[num-1]!=num){  
         A[i]=A[num-1];  
         A[num-1]=num;  
         i--;  
       }  
     }  
     int res=1;  
     while(res-1<A.length && A[res-1]==res) res++;  
     return res;  
   }