题目描述

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.

Solution 1

//用散列表，首先将数字都映射到散列表上，然后，对于每个数字，找到后就删除，然后向两边
//同时搜，只要搜到了就删除，最后求出长度。哈希表搜是O(1),因为每个数字只会添加一次，
//删除一次，所以复杂度是O（n）
 
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
            unordered_set<int> st(num.begin(),num.end());
            int ans=0;
            for(auto v:num){
                if(st.find(v)==st.end()) continue;
                int l=v,r=v;
                st.erase(v);
                while(st.find(r+1)!=st.end()) st.erase(++r);
                while(st.find(l-1)!=st.end()) st.erase(--l);
                ans=max(r-l+1,ans);
            }
            return ans;
    }
};
//PS:说时间复杂度为O(n)觉有点牵强

Solution 2

//排序花的时间复杂度略大
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if(num.size()<=0) return 0;
        if(num.size()==1) return 1;
        sort(num.begin(),num.end());
        int len=1,maxlen=-1;
        for(int i=1;i<num.size();++i)
        {
            if(num[i]-num[i-1]!=0)
            {
                if(num[i]-num[i-1]==1)
                ++len;
            else
                len=1;
            }
            maxlen=max(len,maxlen);
        }
        return maxlen;
    }
};