41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
方法1： 时间复杂度还是 O (n log n)
先将数组排序，从一开始与nums[i] 比较，如果nums[i]<=0 跳过处理，如果重复元素，跳过处理
当nums[i] > target 时，target就是目标值。
class Solution {public int firstMissingPositive(int[] nums) {Arrays.sort(nums);int n = nums.length;int target = 1; // 要找的最小正整数，初始为1for (int i = 0; i < n; i++) {// 跳过负数、0和重复值if (nums[i] <= 0 || (i > 1 && nums[i] == nums[i-1])) {continue;}// 如果当前数等于目标值，目标值+1if (nums[i] == target) {target++;} // 如果当前数大于目标值，说明目标值就是缺失的else if (nums[i] > target) {return target;}}// 遍历完所有数都没返回，说明缺失的是最后一个目标值（比如数组是[1,2,3]，返回4）return target;} }
方法2： 哈希表时间复杂度O(n) ，空间O(n)
public class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;Set<Integer> hashSet = new HashSet<>();for (int num : nums) {hashSet.add(num);}for (int i = 1; i <= len ; i++) {if (!hashSet.contains(i)){return i;}}return len + 1;} }