LintCode: Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

 
/*class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, int> map;
        int ret = 0;
        for(int i : num) {
            if (map.count(i) == 1) continue;
            map[i] = 1;
           
            int low = i, high = i;
             
            // If i-1 appear before, it must be the highest one
            // because this is the first time i is seen        
            if (map.count(i-1) == 1)
                low = i - map[i-1];  

            // If i+1 appear before, it must be the lower bound
            // because this is the first time i is seen
            if (map.count(i+1) == 1)
                high = i + map[i+1];
            int count = high - low + 1;
            ret = max(ret, count);
            map[low] = count;
            map[high] = count;
        }
       
        return ret;
    }
*/
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    int longestConsecutive(vector<int> &num) {
        int ret = 0;
        set<int> mySet(num.begin(), num.end());
        while(mySet.size() > 0) {
            int v = *(mySet.begin());
            int count = 0;
            int up = v;
            while(mySet.erase(up++))
              count++;
            while(mySet.erase(--v))
              count++;
            ret = max(ret, count);
        }
        return ret;
    }
};