描述

给出一个无序的数列，找出其中缺失的第一个正数，要求复杂度为 O(n) 如：[1,2,0]，第一个缺失为3。 如：[3,4,-1,1]，第一个缺失为2。

输入

1,2,0

输出

3

输入样例

1,2,0
3,4,-1,1
-1,-3,-5
1,2,3
-1,-10,0

输出样例

3
2
1
4
1

AC代码：

#include <bits/stdc++.h>
#include<vector>
using namespace std;

int main()
{
    string s;

    while(cin>>s)
    {
        s = s+",";
        bool flag = false;
        vector<int>a;
        a.push_back(0);
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                if(b>0)
                {
                    a.push_back(b);
                }
            }
        }

        vector<int>c(a.size()+1);

        for(int i = 0; i < a.size(); i++)
        {
            if(a[i]<=a.size())
                c[a[i]] = a[i];
        }
        for(int i = 1; i < c.size(); i++)
        {
            if(c[i] == 0)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
}