/*
Longest Consecutive SequenceFeb 14
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given
The longest consecutive elements sequence is
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