First Missing Positive

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.

C++:
01 int firstMissingPositive(int A[], int n) {
02     for(int i=0;i<n;i++){
03        if(A[i]<=0)
04        A[i]=n+1;
05     }
06     for(int i=0;i<n;i++){
07        int t=abs(A[i]);
08        if((t>=1)&&(t<=n)&&(A[t1]>0))
09            A[t1]=-A[t1];
10     }
11     for(int i=0;i<n;i++){
12        if(A[i]>0)
13           return i+1;
14     }
15     return n+1;
16 }
Advertisements
This entry was posted in Array and linked list, Number trick. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s