041 - First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
Hide Tags
Array
 
分析一下，总共三种情况：
1，所有正数从1开始，连续分布，第一个miss的就是最大值加一
2，所有正数从1开始，但不连续，第一个miss的在最大最小值之间
3，所有正数从大于1 的某个数字开始，miss的就是 1 了。
 
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int missed=1;
        int sz=nums.size();
        if(sz)
        {
            int min=INT_MAX, max=INT_MIN;
            for(int ii=0; ii<sz; ++ii)
            {
                int x=nums[ii];
                if(x>0 && x>max)
                    max=x;
                if(x>0 && x<min)
                    min=x;
            }
           
            if(min<=1)
            {
                int* buf = new int[max]();
                for(int ii=0; ii<sz; ++ii)
                    if(nums[ii]>0)
                        buf[nums[ii]-min]=1;
               
                missed=max+1;
                for(int ii=0; ii<max; ++ii)
                    if(!buf[ii])
                    {
                        missed=(min+ii);
                        break;
                    }
                delete[] buf;
            }
        }
        return missed;
    }
};
4 ms.