题目描述
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.
解题思路
这道题最难的地方在于：只能用O(n)的时间复杂度和O(1)的空间复杂度。也就是说，不能简单暴力的将元素放进连续的桶里，并找出空桶。而O(n)的时间复杂度也就意味着不能通过重复遍历数组来找出最小的正数。
在思考了几个小时无果之后，在网上找到了一个这样的思路：由于数组的长度固定，因此可以将其看作一个连续存储正整数的桶。即下标为0的位置放1，1的位置放2.。。。。。即第i个位置放入i+1。将原数组的数尽量按这个规则交换，在最后扫描一遍数组，寻找第一个不符合这个规则的位置的下标就可以找到最小的不在该数组里面的正整数。最差的情况下，所有的数字都能刚好填入，这样返回数组的长度值加一即可。
时间复杂度分析
交换复杂度为O(n)，扫描复杂度最高为O(n)，因此时间复杂度为O(n)。
空间复杂度分析
交换临时变量一个，符合O(1)。
源码
class Solution {
public:
int firstMissingPositive(vector& nums) {
if(nums.size() == 0)
return 1;
int length = nums.size();
for(int i = 0; i < length; ++ i) {
if(nums[i] > 0 && nums[i] != i + 1 && nums[i] < length &&
nums[i] != nums[nums[i] - 1]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
i --;
}
}
for(int i = 0; i < length; ++ i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return length + 1;
}
};
