Leetcode 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的地方，然后从后面开始找只要不是+1，返回那个值就行。但是问题就是题目要求是O(N)，只要涉及排序就变成了log了，所以不能排序，只能考虑遍历。

所以新的思路就来了：我们思考排序的性质，排序后我们需要找到1然后从后面开始找，那么我们是否也可以直接将nums中的值按顺序保存在新的数组中？类似于之前在做统计一个字符串每个单词的个数，我们设置哈希表或者一个26长度的vector一样。 如果是别的题一定是不行的，但这道题只是要找到一个值，所以可以。

所以，遍历nums，将符合[1,nums.size()]的数以该值为下标加入到新的vector中；最终只需遍历到第一个与下标值不符的数即可。

【C++解答】

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        vector<int> tmpVec(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= 1 && nums[i] <= nums.size()) {
                tmpVec[nums[i] - 1] = nums[i];
            }
        }
        for (int i = 0; i < tmpVec.size(); i++) {
            if (tmpVec[i] != i + 1)
                return i + 1;
        }
        return -1;
    }
};