题目链接
LeetCode 41. 缺失的第一个正数[1]
题目描述
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例1
输入： [1,2,0] 输出： 3
示例2
输入： [3,4,-1,1] 输出： 2
示例3
输入： [7,8,9,11,12] 输出： 1
说明：
- 你的算法的时间复杂度应为 ，并且只能使用常数级别的空间。
题解
如果之前一直坚持看我题解的同学，应该前几天刚看过下面这道题：
【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法
韦阳的博客：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法[2]
知乎专栏：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法[3]
那道题是要求 到 中缺失的两个数，于是我们开辟一个大小为 的数组，将所有数字放到下标对应的位置，然后看哪两个位置是空着的。为了使用原地算法，我们直接在原数组上进行操作。
回到本题，我们要寻找的是第一个缺失的正整数。其实问题的本质是一样的，如果数组的长度是 ，那么最多只能填充 到 这 个正整数，所以缺失的正整数一定小于等于 。
那么我们把小于等于 或者大于 的数全部赋值为 ，因为它们是多少不要紧，不影响最后的结果。然后和上面题目方法一样，用原地算法，把每个数字放入对应下标的位置。最后从左到右扫描一遍数组，如果发现有位置是 ，那么第一个缺失的正数就是它了。如果扫描完 到 发现全都在，那么第一个缺失的就是 了。当然可能缺失很多正数，所以扫描到第一个缺失正数之后，就要直接返回结果了。
因为我们要保存 到 之间的数，所以数组长度不够，要在后面扩充一个才行。
时间复杂度是 ，空间复杂度是 。
代码
c++
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); nums.push_back(-1); for (int i = 0; i <= n; ++i) { if (nums[i] <= 0 || nums[i] > n) { nums[i] = -1; } } for (int i = 0; i <= n; ++i) { while (nums[i] != -1 && i != nums[i] && nums[i] != nums[nums[i]]) { swap(nums[i], nums[nums[i]]); } if (nums[i] != -1 && i != nums[i]) { nums[i] = -1; } } for (int i = 1; i <= n; ++i) { if (nums[i] == -1) return i; } return n+1; } };
