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.

Solution: 

Since the complexity requirement is O(N) and the sequence is unsorted, there is only one way to do this, that is to use O(N) space.
Basic idea is to put sequence into a multiset, then choose one element a, find upward, a+1, a+2, and so on, then find downward, i.e., a-1, a-2, ....remember to delete element once find is true

c++ syntax: 
it = multiset.find(a);
multiset.erase(it)

Code:

  int longestConsecutive(vector &num) {
            multiset collec;
    for(size_t i=0; i        collec.insert(num[i]);

    int maxi=0;
    int cnt=0;
    int current;
    multiset::iterator it;
    while(!collec.empty())
    {
         current = *collec.begin();
         cnt++;

         int up=current+1;
         it = collec.find(up);
         while( it!=collec.end() )
         {
             cnt++;
             collec.erase(it);
             up++;
             it = collec.find(up);
         }

         int down = current-1;
         it = collec.find(down);
         while( it!=collec.end() )
         {
             cnt++;
             collec.erase(it);
             down--;
             it=collec.find(down);
         }
        collec.erase(collec.begin());
         if (cnt>maxi)
            maxi = cnt;
        cnt=0;
    }
    return maxi;
    }