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 class Solution {
02 public:
03     int firstMissingPositive(int A[], int n) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         for(int i=0;i<n;i++)
07         {
08             if(A[i]<=0)
09             {
10                 A[i]=n+1;
11             }
12         }
13         for(int i=0;i<n;i++)
14         {
15             int t=A[i];
16             int index=t;
17             if(t<0) index=-t;
18             index;
19             if((index<n)&&(A[index]>0))
20             {
21                 A[index]=-A[index];
22             }
23         }
24         for(int i=0;i<n;i++)
25         {
26             if(A[i]>0) return i+1;
27         }
28         return n+1;
29     }
30 };
Advertisements
This entry was posted in Array and linked list. 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