0041._First_Missing_Positive.md

041.First Missing Positive

难度Hard

刷题内容

原题连接

• https://leetcode.com/problems/first-missing-positive/

内容描述

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1

思路 - 时间复杂度: O(n)- 空间复杂度: O(1)******

刚开始题目的意思理解错了，之后就依次AC了。其实这题如果不加限制条件额外的储存空间，应该会容易想到，直接 hash 表就行，这里我们可以遍历数组，若数组存在1，则在数组的第一个储存1，若2存在，则在数组的第二个位子，依次类推

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