041.md

First Missing Positive

题目

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

example:
Given [1,2,0] return 3,  //1 2 都存在，不存在3 返回3
and [3,4,-1,1] return 2.//1存在 2不存在 返回2

note:Your algorithm should run in O(n) time and uses constant space.

题意：给一个unsorted integer array，从1开始找，如果存在1，则看是否存在2，直到找出数组中第一个不存在的正数。

思路

先得出unsorted integer array的长度size，因为要从1开始寻找，所以答案必定在[1,size+1]内。生成一个长度为size+1的a数组arr,索引0不用。arr的作用 就是记录下每一个小于等于sz的值是否出现过，即更新arr必须满足arr[i] = i;arr下标i的值必定存入i。

遍历一边给定的数组nums，对于nums的每一个值，如果nums[i]<=0 或者 nums[i]>sz 则不做任何处理，否则令arr[nums[i]] = nums[i]。

从下标1开始遍历arr 如果arr[i]!=i 则说明这个数没有出现过,返回i。

如果arr整个数组都更新过了 即总有arr[i] = i 。返回sz+1。

代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int sz = nums.size();
        //创建一个数组长度为sz+1
        vector<int> arr;
        arr.resize(sz+1);
        //令arr[i]的值对应i
        for(int i=0;i<sz;++i){
            if(nums[i]<=sz && nums[i]>0 ){
                arr[nums[i]] = nums[i];
            }
        }
        //返回arr[i]!=i的值
        for(int i=1;i<=sz;++i){
            if(arr[i]==i) continue;
            else return i;
        }
        //否则前sz个数都在，返回sz+1
        return sz+1;
    }
};