MIOJ #4 最长连续数列

描述

输入一个乱序的连续数列,输出其中最长连续数列长度,要求算法复杂度为 O(n) 。

输入

54,55,300,12,56

输出

3

输入样例

100,4,200,1,3,2
54,55,300,12
1
5,4,3,2,1
1,2,3,4,5,6

输出样例

4
2
1
5
6

AC代码:

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

int main()
{
    string s;

    while(cin>>s)
    {
        bool flag = false;
        list<int>a(0);
    int b = 0;
        int j = 0;
        int k = 0;
        s = s +",";
        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(a.size() == 0 && flag == true)
            {
                a.push_back(b);
                //cout<<"1:"<<b<<endl;
            }
            else if(flag == true)
            {
                for( list<int>::iterator it=a.begin(); ; it++)
                {
                    list<int>::iterator it1=a.end();
                    --it1;
                    if(*it > b)
                    {
                        a.insert(it,b);
                       // cout<<"2:"<<b<<endl;
                        break;
                    }
                    if(it == it1)
                    {
                        a.push_back(b);
                       // cout<<"3:"<<b<<endl;
                        break;
                    }
                }
            }
        }

        if(a.size() == 0)
        {
            cout<<"0"<<endl;
        }
        else if(a.size() == 1)
        {
            cout<<"1"<<endl;
        }
        else
        {
            int cnt = 1;
            int maxCnt = 0;
            list<int>::iterator it1=a.begin();
            it1++;
            for( list<int>::iterator it=a.begin(); it1!=a.end(); it++,it1++)
            {
                if(*it+1 == *it1)
                {
                    cnt++;
                    if(cnt > maxCnt)
                    {
                        maxCnt = cnt;
                    }
                }
                else
                {
                    cnt = 1;
                }
            }
            cout<<maxCnt<<endl;
        }
    }
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注