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.

本题是可以用并查集来做，参照之前的摘录：http://www.cnblogs.com/linyx/p/3638222.html

当然也可以用dfs的方式，但是为了O(n)，需要在访问一个元素之后把该元素删掉，删除也需要O(1)，所以用多一个list。

这里的dfs意思是，从数x，去访问x-1,x-2,...，然后访问x+1,x+2,...，边访问边从list删除。这样就需要快速地知道某个数的位置，所以这里用了一个map。

另一点需要注意的是，当从list删除时，map是没有删除的，这里用list.end()来表示某个数已经被删除了，删掉的数就不会再被判断。也就是说，下一次访问到已经访问过的数，或者重复的数，那么map里已经更新为list.end()，所以不会再从这里去dfs，这样保证了不会再删一遍。

首先，每个元素，要么dfs，要么没得dfs。dfs是在list上做的，list的长度随着dfs递减，所以整个开销为O(n)。

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.empty()) return 0;
        map<int, list<int>::iterator> len;
        int n = num.size();
        list<int> copy;
        for (int i = 0; i < n; ++i) {
            copy.push_front(num[i]);
            len[num[i]] = copy.begin();
        }
        int max = 0;
        for (int i = 0; i < n; ++i) {
            if (len[num[i]] == copy.end()) continue;
            int l = 1;
            while (len.find(num[i] - l) != len.end()) { 
                copy.erase(len[num[i] - l]);
                len[num[i] - l] = copy.end();
                l++;
            }
            int u = 1;
            while (len.find(num[i] + u) != len.end()) {
                copy.erase(len[num[i] + u]);
                len[num[i] + u] = copy.end();
                u++;
            }
            if (l + u - 1 > max) {
                max = l + u - 1;
            }
            len[num[i]] = copy.end();
        }
        return max;
    }
};