题目：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 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
一、模式识别
本题较难，无法直接找到模式，需要单独分析：
题解原话：
「真正」满足时间复杂度为 O(N) 且空间复杂度为 O(1) 的算法是不存在的，但是我们可以退而求其次：利用给定数组中的空间来存储一些状态。也就是说，如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法；但如果我们可以修改给定的数组，那么是存在满足要求的算法的。
思路一：把nums从数组变成集合（不知道算不算？），这样就可以ON线性遍历查找了
思路二：从 1 开始依次枚举正整数，并遍历数组，判断其是否在数组中
遍历数组找数字，排除其他数字，将[1, N]内的数字放入对应索引位置，
我这里用一下官方题解的图：
二、代码实现
1.数组变集合
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:nums = set(nums)ans = 1while ans in nums: ans += 1return ans2.多次遍历标记数组
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):if nums[i] <= 0: nums[i] = n + 1for i in range(n):num = abs(nums[i])if num <= n: nums[num - 1] = -abs(nums[num - 1])for i in range(n):if nums[i] > 0: return i + 1return n + 13.置换数组
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]for i in range(n):if nums[i] != i + 1: return i + 1return n + 1
