Description

Link: https://oj.leetcode.com/problems/first-missing-positive/

Solution

 1 class Solution {
 2 public:
 3     int firstMissingPositive(int A[], int n) {
 4     	for (int i =0; i < n; ++ i)
 5     		if (A[i] == -1)
 6     			A[i] = -3;
 7 
 8         for (int i = 0; i < n; ++ i){
 9         	if (A[i] > n || A[i] < 1)        		
10         		continue;
11         	int tp = A[i];
12         	while (tp-1 > i && tp-1 < n){
13         		int cache = A[tp-1];
14         		A[tp-1] = -1;
15         		tp = cache;
16         	}
17         	if (tp <= n && tp >= 1)
18         		A[tp-1] = -1;
19         }
20        
21         for (int i = 0; i < n; ++ i){
22         	if (A[i] != -1)
23         		return i + 1;
24         }
25         return n+1;
26     }
27 };

Analysis

This problem requires using $O(n)$ time and $O(1)$ space. Thus we re-use the array A[] to record which positive number has appeared.

In my algorithm, I use A[i] = -1 to mark the appearance of the positive number i+1, however, it is possible that some A[j] = -1 in the first place. Thus we preprocess A[] changing all navtive -1 into -3.

Then in every loop $i$, we mark A[A[i]-1] = -1. One problem is that, maybe A[i]-1 is greater than i, which means A[A[i]-1] has not been visited yet, if we blindly change A[A[i]-1] to -1 to mark the appearance of A[i], we will lose the information about A[A[i]-1].

Therefore, I use a while loop to up at line 12 to solve this problem. Whenever we meet a A[i], where A[i]-1 > i, we cache tp = A[A[i]-1] and change A[A[i]-1] to -1, then we do the same thing to the cached tp, until we find tp <= i or tp is not legal (negative or above n).

Time complextiy

• In the preprocess step is $O(n)$.
• In the loop part, A[j] will be visited if
  • i = j
  • or $\exists k, A[k]-1 = j$

So the total time of visits is at most $2n$, which means the time complexity of this algorithm is $O(n)$.