LeetCode----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：最简单的方法是 先排序， 然后扫描一遍数组。。复杂度是 O(nlgn) 不符合要求

思路 2：用 hash表 记录 n 个元素。

             然后扫描数组，如果当前元素在 Hash 表中存在，求其所在的最大连续区间（向左，向右延伸）在搜索的过程中 删除 Hash 表中对应的元素。

                                      如果当前元素在 Hash 表中不存在，这个元素要么不存在，要么被 删除了， 跳过。

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> visited(num.begin(), num.end());
        int len(0), longest(0);
        
        for(vector<int>::iterator it = num.begin(); it != num.end(); ++it){
            if(visited.find(*it) == visited.end()) continue;
            len = 0;
            //向后延伸
            for(int i=*it; visited.find(i)!=visited.end(); ++i, ++len)
              visited.erase(i);
            //向前延伸
            for(int i=*it-1; visited.find(i)!=visited.end(); --i, ++len)
              visited.erase(i);
            longest = max(longest, len);
        }
        return longest;
    }
};

LeetCode----Longest Consecutive Sequence

原文：http://blog.csdn.net/shoulinjun/article/details/19249039