Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0] Output: 3
Example 2:
Input: [3,4,-1,1] Output: 2
Example 3:
Input: [7,8,9,11,12] Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
Related Topics:
Array
Similar Questions:
- Missing Number (Easy)
- Find the Duplicate Number (Medium)
- Find All Numbers Disappeared in an Array (Easy)
- Couples Holding Hands (Hard)
// OJ: https://leetcode.com/problems/first-missing-positive/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int firstMissingPositive(vector<int>& A) {
int i, N = A.size();
for (i = 0; i < N; ) {
if (A[i] == i + 1 || A[i] < 1 || A[i] >= N + 1 || A[i] == A[A[i] - 1]) ++i;
else swap(A[i], A[A[i] - 1]);
}
for (i = 0; i < N && A[i] == i + 1; ++i);
return i + 1;
}
};