来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
题目描述
给你一个未排序的整数数组 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 * 105
-231 <= nums[i] <= 231 - 1
解题思路
理论上并不存在时间复杂度为O(n) 空间复杂度为 O(1)的算法来做这道题，所以需要借助题目提供的nums来解，nums的范围为n，那么可以利用nums来判断1-n中是否有数字出现，如果没有，那么最小正整数为n+1，否则就是第一个缺失的数字。
一个思路是利用负号来记录1-n中数字是否出现过，先将所有负数变成n+1，然后遍历，如果数字x出现就将数字x对应的下标x-1的值设置为负数，等结束后第一个正数的下标加一就是缺失的数字。
另一个思路是重置归位，将1-n中的数字重置到nums对应的位置上并且继续重置被交换的数，那么第一个错位的数字就是缺失的数字。注意由于nums中数字可能相同，所以交换的双方相等就可以结束交换继续遍历。
代码展示
负号做标记
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++) { if(nums[i] <= 0) nums[i] = n + 1; } for(int i = 0; i < n; i++) { if(abs(nums[i]) < n + 1) nums[abs(nums[i]) - 1] = nums[abs(nums[i]) - 1] < 0 ? nums[abs(nums[i]) - 1] : -1 * nums[abs(nums[i]) - 1]; } for(int i = 0; i < n; i++) if(nums[i] > 0) return i + 1; return n + 1; } };
置换
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++) { while(nums[i] > 0 && nums[i] < n + 1 && nums[i] != nums[nums[i] - 1]) { swap(nums[i], nums[nums[i] - 1]); } } for(int i = 0; i < n; i++) if(nums[i] != i + 1) return i + 1; return n + 1; } };
运行结果
