1. 题目
给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
2. 示例
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
3. 解法：标记法
public class Solution17 {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 1. 遍历数组，将小于等于0的数字替换为一个大于数组长度的数
for (int i = 0; i < n; i++) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
// 2. 标记位置上的数，如果出现过为负数，
for (int i = 0; i < n; i++) {
int num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// 3. 找到第一个正数
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}
