LeetCode - First Missing Positive

时间：2014-02-09 16:16:06 收藏：0 阅读：383

2014.2.8 23:43

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.

Solution1:

　　The first solution I thought of was hashing, using unordered_map. This promises O(n) time, but not constant space.

　　Solution is simple and runs in one pass. I guess the code can explain itself.

　　Time and space complexities are both O(n).

Accepted code:

 1 // 1AC, unordered_map is a good substitute for map
 2 #include <unordered_map>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     int firstMissingPositive(int A[], int n) {
 8         if (A == nullptr || n <= 0) {
 9             return 1;
10         }
11         
12         unordered_map<int, int> um;
13         int result;
14         int i;
15         
16         result = 1;
17         for (i = 0; i < n; ++i) {
18             if (A[i] > result) {
19                 um[A[i]] = 1;
20             } else if (A[i] < result) {
21                 continue;
22             } else {
23                 um[result] = 1;
24                 ++result;
25                 while (um.find(result) != um.end()) {
26                     ++result;
27                 }
28             }
29         }
30         
31         um.clear();
32         return result;
33     }
34 };

Solution2:

Accepted code:

原文：http://www.cnblogs.com/zhuli19901106/p/3541168.html