给你一个未排序的整数数组 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
方法一：最简单的思路，hash表把所有正数存下来，然后遍历hash表，缺失值就找到了。（比官方的易理解，官方是用数组标记）
class Solution { public: int firstMissingPositive(vector<int>& nums) { unordered_map<int,int> hash; for(int i=0;i<nums.size();i++){ if(nums[i]>0)hash[nums[i]]++; } int res=0; while(hash[++res]); return res; } };
leetcode官方 ：
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; } };
方法二：置换法(详细注释)
除了打标记以外，我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：
如果数组中包含 x∈[1,N]，那么恢复后，数组的第 x−1个元素为 x。
在恢复后，数组应当有 [1, 2, ..., N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2。
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); // 获取数组的长度 // 第一次遍历数组，将每个正整数 nums[i] 放置到索引为 nums[i] - 1 的位置上 // 即将 1 放到索引 0，将 2 放到索引 1，以此类推，直到 n 放到索引 n - 1 for (int i = 0; i < n; ++i) { // 只处理大于 0 且小于等于 n 的元素，并且确保 nums[i] 不在正确位置上 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { swap(nums[nums[i] - 1], nums[i]); // 将 nums[i] 放到正确的位置上 } } // 第二次遍历数组，找到第一个不在正确位置上的数，即缺失的最小正整数 for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { // 如果 nums[i] 不等于 i + 1，表示缺失 i + 1 return i + 1; } } // 如果数组中包含 1 到 n 的所有正整数，则缺失的是 n + 1 return n + 1; } };
方法三：原线性表标记
设数组的长度为n，那么答案一定是在[1, n + 1]之间的一个整数，最坏的情况是1到n都出现在数组中了，即答案会是n+1，否则一定会缺少其中某个数字，那么问题就转化成了统计数组中1到n的出现情况；
难点就在于如何只用常数级别的额外空间，这时候就可以想到使用原数组去标记，因为数组的长度正好就是n；
首先遍历一次数组，让本身小于等于0或大于n的数全部变成0，这样就会让数组中只留下[1, n]之间的数，方便我们后续处理；由于出现的不同数字个数是小于等于n的，因而原数组的空间肯定是足够的；
再次遍历数组，对于每个大于0的数t(即在[1, n]内)，我们令nums[t - 1] = -1，用于标记t出现在数组中过；此外在修改nums[t - 1]前，先用一个临时变量x保存nums[t - 1]的值，如果发现x > 0，则还需要迭代地进行标记，直到最后标记的位置的原始值为0或-1(0表示这个地方原来的值不在[1,n]之间，这个值我们不关心从而该位置可以被随意使用；-1表示这个地方已经被标记过)；
- 最后遍历一次数组，nums[i] = -1表示i+1出现过，所以当第一次发现nums[i]不为-1时就可以返回i + 1了；如果全都是-1则表示[1, n]全部出现了，返回n + 1。
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(), ans = n + 1; // 获取数组长度，并初始化结果为 n+1 auto judge = [&](int x){return x >= 1 && x <= n;}; // 定义 lambda 表达式，用于判断数字是否在有效范围内 for(int& m : nums){ // 将不在有效范围内的数字置为 0 if(!judge(m)) m = 0; } for(int i = 0; i < n; i ++){ // 将出现过的正整数标记在数组中，负数表示已经出现过 if(nums[i] > 0){ int t = nums[i]; nums[i] = 0; while(t > 0){ // 不断迭代，直到 t <= 0 int x = nums[t - 1]; nums[t - 1] = -1; // 将出现过的正整数标记为 -1 t = x; } } } for(int i = 0; i < n; i ++){ // 寻找第一个未被标记的数，其索引 + 1 即为结果 if(nums[i] != -1){ ans = i + 1; break; } } return ans; // 返回结果 } };
