标签：数组，难
问题描述
Given an unsorted integer array, find the smallest missing positive integer.
给定未排序整型数组，查找缺失的最小正整数。
示例:
输入: [1,2,0]
输出: 3
输入: [3,4,-1,1]
输出: 2
输出: [7,8,9,11,12]
输出: 1
注意:
算法运行时间 在O(n)内，且使用空间复杂度为常量。
解决方案
比较直观的想法是先对数组进行排序，然后遍历数组查找缺失的最小正整数。但是本题要求运行时间在O(n)内，常见排序算法的时间复杂度无法满足。
方法一：
使用位图存储每个出现的正整数，然后遍历正整数寻找未出现过的整数。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unsigned char *bitmap = new unsigned char[1<<28];
int result;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] <= 0)
continue;
int idx = nums[i] / 8;
int bit = nums[i] % 8;
bitmap[idx] = bitmap[idx] | 1 << bit;
}
for(int i = 1; i <= INT_MAX; i++) {
int idx = i / 8;
int bit = i % 8;
if((bitmap[idx] & (1 << bit)) == 0)
return i;
}
return result;
}
};
算法分析：
- 时间复杂度：Θ(n)
- 空间复杂度：O(1)。本题中额外存储空间量为228字节。
- 运行时间：4ms
方法二：
核心思想是把A[i]放到位置A[i] - 1处。这需要两次遍历数组。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
if(len == 0)
return 1;
int i = 0;
while(i < len) {
if(nums[i] <= 0 || nums[i] > len)
i++;
else if(nums[nums[i] - 1] == nums[i]) {
i++;
} else {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for(i = 0; i < len; i++) {
if(nums[i] != i + 1)
return i+1;
}
return i + 1;
}
};
算法分析：
- 时间复杂度：Θ(n)
- 空间复杂度：O(1)。
- 运行时间：4ms
