LeetCode 题解 41. 缺失的第一个正数
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
题解
题目看起来很简单，寻找未出现过的最小正整数
很自然的想法就是用哈希表统计各个数字出现的次数，然后从1开始递增寻找是否出现过，第一个未出现的数字就是答案
但是注意到题目的要求是只使用常数级别额外空间的解决方案，也就是说不能开辟一个哈希表，需要在原数组上进行操作
接着对题目进行分析，我们发现：对于 n 个数的数组，最大的答案为 n+1，即数组内是 1，2，3…n 这些数各一个
否则只要有任何一个 1~n 之外或者重复的数，那么1~n之间必定有数字没出现，最小的即为我们的答案
- 所以答案在 1~n+1 之间，而对于数组我们只关心 1~n 之间的数字，其余的数字对答案没有影响
接下来我们考虑如何在数组内原地操作
由于我们仅关心 1~n 的数字，而原数组恰好又是 n 大小，不妨将原数组作为哈希表，记录 1~n
用 nums[i] 记录 i+1
我们并不能直接用 nums[i] 记录 i+1 出现的次数，因为原数组内存储着需要的数据，不能直接修改原数组中的数据
那么我们不妨“一个萝卜一个坑"，将 nums[i] 放到下标为 nums[i]-1 的位置上，并且考虑到不能修改原数组，我们将 nums[i] 与 nums[nums[i]-1] 进行交换，于是我们遍历数组，将数字放到对应的位置上，最后再遍历数组，第一个数字与位置不对的位置就是我们的答案
实现细节
- 遍历数组，此时位置为 i
- 如果 nums[i] 在 1~n 之外，我们不用处理它，因为它对答案没有影响
- 如果 nums[i] 在 1~n 之间，我们需要判断位置 nums[i]-1 上是否已经放置了对应的数 num[i]（
它是否在位置 nums[i]-1 上） ，没有的话就将其与对应位置的数进行交换，否则同样不做处理 - 然后我们接着看位置 i 上换来的新数据，重复以上过程
- 位置 i 处理结束后 i++
- 注意，数组中会含有重复的数据
因此步骤3我们不能去直接判断数字 nums[i] 是否在对应位置 nums[i]-1 上
因为位置 nums[i]-1 上的数可能是另一个 nums[i]，这样我们交换后再看换来的 nums[i]，由于 nums[i] 不在对应位置，会接着把之前换过去的 nums[i] 换回来，这样就死循环了
为了应对这种情况，我们直接去判断 nums[i] 对应的位置上是否是正确的数，是正确的数就不用处理了，多余的数和范围外的数一样对答案没有影响，这样面对重复的数字就不会一直交换了
代码如下↓
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();int res=n+1;for(int i=0;i<n;i++){if(nums[i]>=1 && nums[i]<=n && nums[i]!=nums[nums[i]-1]){swap(nums[nums[i]-1],nums[i]);i--;}}for(int i=0;i<n;i++){if(nums[i]!=i+1){res=i+1;break;}}return res;}
};