Lintcode: longest consecutive sequence

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

Have you met this question in a real interview? 

Yes

Example

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

Clarification

Your algorithm should run in O(n) complexity.

Reference:
Thought:
http://yucoding.blogspot.com/2013/05/leetcode-question-129-longest.html
Codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-longest-consecutive-sequence.html


Time: O(n)
Space: O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: /** * @param nums: A list of integers * @return an integer */ int longestConsecutive(vector<int> &num) { unordered_set<int> hash; for(int i = 0;i < num.size(); i++){ hash.insert(num[i]); } int maxLen = 0; for(int i = 0; i < num.size(); i++){ if(hash.empty()) break; int curLen = 0; int curNum = num[i]; while(hash.count(curNum)){ hash.erase(curNum); curLen++; curNum++; } curNum = num[i] - 1; while(hash.count(curNum)){ hash.erase(curNum); curLen++; curNum--; } maxLen = max(maxLen, curLen); } return maxLen; } };

Lintcode second:
Good codes
http://www.geeksforgeeks.org/longest-consecutive-subsequence/

Time: O(nlogn)
Space: O(1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: /** * @param nums: A list of integers * @return an integer */ int longestConsecutive(vector<int> &num) { // write you code here if(num.size() == 0) return 0; //if(num.size() == 1) return 1; sort(num.begin(), num.end()); int maxLen = 1; for(int i = 1; i < num.size(); i++){ if(i == 0) continue; int tempLen = 1; while(i < num.size() && (num[i] == num[i - 1] + 1 || num[i] == num[i - 1])){ if(num[i] == num[i - 1] + 1){ tempLen++; } i++; } maxLen = max(tempLen, maxLen); } return maxLen; } };