地址

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

题目

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.

思路

如果没用空间限制,直接哈希即可:开个标记数组,然后把出现过的数的位置标为1,然后从1开始扫到的第一个为0的位置即是答案。
有空间限制的话,借助上面的思路,把题目所给的数组当作标记数组应用即可。下面举例说明做法:
假如有数组a[4,5,3,2,6],从左向右扫到第一个数4,那么把a[4]位置打个标记让a[4]=flag,同时取出原a[4]上的数2。重复同样的工作,让a[2]=flag,然后从原a[2]的数5继续开始,让a[5]=flag,之后因为原a[5]:6大于数组大小5所以不管。
这样一轮之后数组a变成了[4,flag,3,flag,flag],然后从下一个非flag数3重复上面的算法,最后得到[4,flag,flag,flag,flag]。最后第一个非flag位置即是第一个没出现的数,如果数组中不存在不是flag的位置,那么size(a)+1就是第一个没出现的数。
这题有非正数,遇到非正数时直接跳过即可,flag用一个不会出现的数表示比如-1e9-7。

代码

class Solution {
public:
    int firstMissingPositive(vector<int>& num) {
        int ff=-1e9-7,n=num.size(),ans=n+1;
        for(int i=0;i<n;i++)
        if(num[i]<=0)
            continue;
        else
        {
            for(int j=num[i],t;j>0&&j<=n;t=num[j-1],num[j-1]=ff,j=t)
                ;
        }
        for(int i=0;i<n;i++)
        if(num[i]!=ff)
        {
            ans=i+1;
            break;
        }
        return ans;
    }
};