First Missing Positive
文章目录
First Missing Positive 题解
题目描述
即从无序的数组中找出第一个缺失的正整数,要求时间复杂度为O(n),空间复杂度为O(1)。
如:[3,4,-1,1],第一个缺失的正整数为2。
题解
可以利用数组索引来记录数组出现的正数,即将数组索引号对应正数。具体下来就是将数组array中的x(1<=x<=n)存储到array[x-1]中。最后从0开始遍历数组,第一次出现array[i] != i+1,则数组中没有i这个正整数,也就是数组中第一个缺失的正整数。将x(1<=x<=n)存储到array[x]中也是只需遍历一次数组,所以时间复杂度为O(n)。而这过程只需要常数个变量就可以完成替换存储,所以空间复杂度为O(1)。
例如[3,4,-1,1]。则变成[1,-1,3,4],第一个缺失正整数是2。
代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
size_t n = nums.size();
for (int i = 0; i < n; ) {
int tmp = nums[i] - 1;
if (tmp == i || tmp < 0 || tmp >= n || nums[tmp] == tmp + 1) {
++i;
} else {
nums[i] = nums[tmp];
nums[tmp] = tmp + 1;
}
}
for (size_t i = 0; i < n; ++i) {
if (nums[i] != i + 1)
return i + 1;
}
return n + 1;
}
};
总结
主要应用了索引映射正数这一技巧。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论