问题描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
提示：
1 <= nums.length <= 5 * 10⁵-2³¹ <= nums[i] <= 2³¹ - 1
解题思路
标记
在nums[i]数组上做标记，我们可以将nums数组中的负数都设为n + 1，令num = abs(nums[i])，然后将nums[num - 1]取反，最后遍历修改后的nums[i]，如果都是负数，返回n + 1，否则返回碰到的第一个非负数的索引加一；
置换
如果nums[i] <= nums.size() && nums[i] > 0，那么就将它与nums[num[i] - 1]置换，为了防止死循环，还要判断nums[i] != nums[nums[i] - 1]
代码
标记
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int& num: nums) {
if (num <= 0) {
num = n + 1;
}
}
for (int i = 0; i < n; ++i) {
int num = abs(nums[i]);
if (num <= n) {
nums[num - 1] = -abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
};
// @lc code=end
置换
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
std::swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.size() + 1;
}
};