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] 进行交换，于是我们遍历数组，将数字放到对应的位置上，最后再遍历数组，第一个数字与位置不对的位置就是我们的答案

实现细节

1. 遍历数组，此时位置为 i
2. 如果 nums[i] 在 1~n 之外，我们不用处理它，因为它对答案没有影响
3. 如果 nums[i] 在 1~n 之间，我们需要判断位置 nums[i]-1 上是否已经放置了对应的数 num[i]（它是否在位置 nums[i]-1 上） ，没有的话就将其与对应位置的数进行交换，否则同样不做处理
4. 然后我们接着看位置 i 上换来的新数据，重复以上过程
5. 位置 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;
    }
};