[leetcode] Longest Consecutive Sequence

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.

思路：

思路就是把所有的数据存在一个hash表中，从表中的第一个元素开始，依此寻找与它相邻的元素，直到找不到相邻的，这就是一个相邻数字的长度。然后在重复上面的步骤。

这题还有一个关键，开始写的时候没有AC，没有erase哈希表中已经找到的元素，数据太大就会TLE，看了别人的才发现这个问题。细节处理的不好。

题解：

class Solution {
public:
    typedef unordered_set<int> Hash;
    int longestConsecutive(vector<int> &num) {
        Hash hash;
        Hash::iterator it;
        Hash::iterator it1;
        for(int i=0;i<num.size();i++)
            hash.insert(num[i]);
        int result = 0;
        int tmp = 0;
        int max = 0;
        while(!hash.empty()) {
            it = hash.begin();
            int elem = *it;
            tmp = elem+1;
            max = 1;
            hash.erase(it);
            while((it1=hash.find(tmp))!=hash.end()) {
                max++;
                tmp++;
                hash.erase(it1);
            }
            tmp= elem-1;
            while((it1=hash.find(tmp))!=hash.end()) {
                max++;
                tmp--;
                hash.erase(it1);
            }
            if(max>result)
                result = max;
        }
        return result;
    }
};