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.
想法一:
用01数组代表该数字是否存在序列中,化归为:一个01序列中,最长连续1的问题。
小数据上可以,但是大数据测试上遇到了问题,当数据跨度很大,比如INT_MIN~INT_MAX时,空间复杂度太高。
想法二:
用map代替数组实现上面的想法,可以解决空间复杂度问题。
但是在计算最长连续1的过程中发现新的问题,遍历INT_MIN~INT_MAX的时间复杂度太高。
参考了Discussion中的一些讨论,
想法三:
对1的元素进行左右最大扩展计数,访问过的元素置0防止计数冗余,代替全范围的遍历计数。
class Solution { public: int longestConsecutive(vector<int> &num) { map<int, bool> tag; for(vector<int>::size_type i = 0; i < num.size(); i ++) {// true 代表未访问过 tag[num[i]] = true; } int count = 0; for(vector<int>::size_type i = 0; i < num.size(); i ++) { int curcount = 0; if(tag.find(num[i]) != tag.end() && tag[num[i]] == true) { tag[num[i]] = false; curcount ++; int left = num[i]-1; while(tag.find(left) != tag.end() && tag[left] == true) { tag[left] = false; curcount ++; left -= 1; } int right = num[i]+1; while(tag.find(right) != tag.end() && tag[right] == true) { tag[right] = false; curcount ++; right += 1; } if(curcount > count) count = curcount; } } return count; } };
【LeetCode】Longest Consecutive Sequence,布布扣,bubuko.com
【LeetCode】Longest Consecutive Sequence
原文:http://www.cnblogs.com/ganganloveu/p/3704176.html