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:
LeetCode - First Missing Positive
原文：http://www.cnblogs.com/zhuli19901106/p/3541168.html