My O(n) and constant space solution in C++ which cost 8ms, can anyone be faster?


  • 1
    S
    int firstMissingPositive(int A[], int n) {
    if(n==0)
        return 1;
    for (int i(0); i != n;)
    {
    	if (A[i] != i + 1 && A[i]>0 && A[i] <= n&& A[A[i]-1] != A[i])
    	{
    		swap(A[i], A[A[i] - 1]);
    	}
    	else ++i;
    }
    for (int i(0); i != n; ++i)
    {
    	if (A[i] != i + 1)
    		return i + 1;
    }
    return n+1;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.