Lintcode124 Longest Consecutive Sequence solution 题解

【题目描述】

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

给定一个未排序的整数数组,找出最长连续序列的长度。

【题目链接】

www.lintcode.com/en/problem/longest-consecutive-sequence/

【题目解析】

1.对于每一个n,检查是否为一个consecutive sequence的边界,也就是n-1不存在于set中,再逐次检查n + 1, n + 2, n + 3…是否在set中,最终得到另一个上边界(+1)m,所以sequence的长度为m – n (也可以是n+1不存在于set中,则反向检查)。转为set,时间O(n),之后对于set中的每一个元素,如果是一个连续序列的下边界,则对这个连续序列进行,因为对于每一个连续序列实际只会扫描一遍,所以这个循环最终是O(n)时间复杂度的。

【参考答案】

www.jiuzhang.com/solutions/longest-consecutive-sequence/

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.