题目描述
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]
观察一下可以发现，如果数组内部包含了所有正数的话，正数的范围应该是在 1 ～ n 里面，而且最大不会超过 n；所以有几类数字我们可以不用关注：0，负数，超过 n 的正数；然后发现数字和 n 有关系的话，可以想到利用数组的位置来作为标志存放遇到的正数。比如将上面第三个例子排列成如下方式：
[4, 3, 2, -1, 5, 6]
// after
[x, 2, 3, 4, 5, 6]
这样我们只要扫描遇到 index（+1）和其元素不相同的第一个就可以发现缺失的第一个正数了；因此只需要扫描一遍数组，将所有 1 ～ n 范围内的正数放在正确的位置，注意每次更换一次都要确保换回来的数字要么是正确的，要么是不需要的数字，否则要继续更换，然后再扫描一遍就可以知道结果，代码如下。
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;
}
};
时间复杂度： O(n) 空间复杂度： O(1)