Tuesday, February 19, 2013

Longest Consecutive Sequence (Incomplete)


/*

Longest Consecutive SequenceFeb 14
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.   */

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if (size==0) return 0;
       
        int const MAX = 4000;
        vector<bool> bitMap;
        int i;
       
        for(i=0; i<MAX; i++){
            bitMap.push_back(false);
        }
       
        for(i=0; i<size; i++){
            //--todo how to deal with overflow
            if(num.at(i)>MAX) return 0;
            bitMap.at(2000+num.at(i)) = true;
        }
       
        int result = 0;
        int currentLength;
        i = 0;
        while(i<MAX){
            currentLength = 0;
            while(bitMap.at(i)==true && i<MAX){
                currentLength++;
                i++;
            }
            if(currentLength > result) result = currentLength;
            i++;
        }
       
        return result;
    }
};

No comments:

Post a Comment