# First Missing Positive

## Question

### Problem Statement

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.

## 题解

### C++

class Solution {
public:
/**
* @param A: a vector of integers
* @return: an integer
*/
int firstMissingPositive(vector<int> A) {
const int size = A.size();

for (int i = 0; i < size; ++i) {
while (A[i] > 0 && A[i] <= size && \
(A[i] != i + 1) && (A[i] != A[A[i] - 1])) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
}
}

for (int i = 0; i < size; ++i) {
if (A[i] != i + 1) {
return i + 1;
}
}

return size + 1;
}
};


### Java

public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null) return -1;

for (int i = 0; i < nums.length; i++) {
while (nums[i] > 0
&& nums[i] <= nums.length
&& nums[i] != i + 1
&& (nums[i] != nums[nums[i] - 1])) {

int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}

for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) return i + 1;
}

return 1 + nums.length;
}
}


### 源码分析

1. A[i] 为正数，负数和零都无法在桶中找到生存空间...
2. A[i] \leq size 当前索引处的值不能比原数组容量大，大了的话也没用啊，肯定不是缺的第一个正数。
3. A[i] != i + 1, 已满足条件了无需交换。
4. A[i] != A[A[i] - 1], 避免欲交换的值和自身相同，否则有重复值时会产生死循环。

int temp = A[i];
A[i] = A[A[i] - 1];
A[A[i] - 1] = temp;


### 复杂度分析

「桶排序」需要遍历一次原数组，考虑到while循环也需要一定次数的遍历，故时间复杂度至少为 $O(n)$. 最后求索引值最多遍历一次排序后数组，时间复杂度最高为 $O(n)$, 用到了temp作为中间交换变量，空间复杂度为 $O(1)$.