Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

思路：这道题求出最长连续数组，先从小到达排序，然后删除重复元素，在进行循环比较；如果相邻的元素相差为1，这maxlen加1，如果不是则maxlen=1，result[maxlen]=A[i]重新来过。但是这道题要求时间复杂度是O(n)，用到排序了时间复杂度变为O(nlogn).

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        int n=num.size();
        if(n<=1)
            return n;
        sort(num.begin(),num.end());
        num.erase(unique(num.begin(),num.end()),num.end());
        int maxlen=1;
        int result[n];
        result[maxlen]=num[0];
        int length=1;
        for(int i=1;i<num.size();i++)
        {
            if(num[i]-num[i-1]==1)
            {
                result[maxlen++]=num[i];
            }
            else
            {
                maxlen=1;
                result[maxlen]=num[i];
            }
            if(maxlen>length)
                length=maxlen;
        }
        return length;
    }
};

解法二：时间复杂度为O(n)，从当前元素递减寻找，从当前元素+1递增寻找，这样一次就能够把连续序列找全。找全后，别忘记清空元素，保证下次不会重复寻找，以减少重复搜寻的次数。

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        map<int,int> result;
        for(int i=0;i<num.size();i++)
        {
            result[num[i]]=1;
        }
        int maxlen=0;
        for(int i=0;i<num.size();i++)
        {
            int sum=1;
            if(result.count(num[i]))
            {
                result[num[i]]=0;
                int left=num[i]-1;
                while(result.count(left)&&result[left]!=0)
                {
                    result[left]=0;
                    left--;
                    sum++;
                }
                int right=num[i]+1;
                while(result.count(right)&&result[right]!=0)
                {
                    result[right]=0;
                    right++;
                    sum++;
                }
            }
            if(maxlen<sum)
                maxlen=sum;
        }
        return maxlen;
    }
};