## [Leetcode]41. First Missing Positive

### 题目描述

Given an unsorted integer array, find the smallest missing positive integer.

### 例子

#### 例子 1

Input: [1,2,0] Output: 3

#### 例子 2

Input: [3,4,-1,1] Output: 2

#### 例子 3

Input: [7,8,9,11,12] Output: 1

#### 要求

Your algorithm should run in O(n) time and uses constant extra space.

### 题目思路

``````[4, 3, 2, 1, 5, 6]
[4, 3, 2, 1, 5, 7]
[4, 3, 2, -1, 5, 6]
[4, 3, 2, 1, 5, -6]
``````

``````[4, 3, 2, -1, 5, 6]

// after
[x, 2, 3, 4, 5, 6]
``````

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();

int index = 0;
while (index < n) {
while (nums[index] > 0 && nums[index] <= n && nums[index] != index + 1) {
int correct_index = nums[index] - 1;
if (nums[index] == nums[correct_index]) {
break;
}
swap(nums[index], nums[correct_index]);
}
index++;
}

int first_missing_positive = n + 1;
for (int i = 0; i < n; i++) {
if (nums[i] != (i + 1)) {
first_missing_positive = i + 1;
break;
}
}

return first_missing_positive;
}
};
``````