1. 题目

First Missing Positive

2. 算法

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

3.代码

http://www.cnblogs.com/grandyang/p/4395963.html

array

• 遍历数组，存入hash表
• 找出最大值
• 下次循环从1开始，递增找数字
• 哪个数字找不到，就返回哪个数字

• 如果一直找到了最大值，返回最大值+1

• 空间复杂度是o(n)

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        if(n<=0)  return 1;
        unordered_map<int,int>  m;
        int mx=nums[0];
        for(int i=0;i<n;i++){
            if(nums[0]>0){
                m[nums[i]]=i;
                mx=max(mx,nums[i]);
            }
        }

        for(int i=1;i<=mx;++i)
            if(m.find(i)==m.end()) 
                return i;
        return mx+1;

    }
};

sway

• 覆盖原有数组，空间复杂度是o(1)
• 将1放在nums[0],2放在nums[1]
• nums[i]放在nums[nums[i-1]]的位置
• 遍历数组，如果nums[i]!=i+1，而nums[i]为整数,而A[i]为整数且不大于n，另外A[i]不等于A[A[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，

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

        for(int j=0;j<n;j++)
            if(nums[j]!=j+1)
                return j+1;
        return n+1;
    }
};