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.
The key point is that for each number say Val in the array, we only need to determine whether its neighbor (Val-1 and Val+1) is in the array and for a consecutive sequence we only need to know the the boundary and the length information。
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 < 2) return size; map<int, int> myMap; for(int i = 0; i< num.size(); i++) myMap.insert(pair<int, int>(num[i],1)); int maxLen = 0; map<int, int>::iterator m_it; map<int, int>::iterator temp_it; for(m_it = myMap.begin(); m_it != myMap.end();m_it++) { if(m_it->second == 0) continue; int len = 1; int low = m_it->first; int high = low; while(true) { temp_it= myMap.find(low-1); if(temp_it == myMap.end()) break; low--; len++; temp_it->second = 0; } while(true) { temp_it= myMap.find(high+1) ; if(temp_it == myMap.end()) break; high++; len++ ; temp_it->second = 0; } maxLen = maxLen < len ? len : maxLen ; } return maxLen ; } };