博文中会简要介绍Leetcode P0128题目分析及解题思路。
“Longest Consecutive Sequence”这道并不算难,但是思路比较巧妙。总体来说有两种思路,一种是通过并查集(Union Find)来不断延长序列长度;另一种则是每次从可能的连续区间最左值开始自增遍历,由此得到连续区间的长度。
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
第一种并查集的思想并不多见,但是也是一个很重要的解题思路。下述Java代码中的第一种解法就借鉴了并查集的思想。对于一个数n
而言,n+1
、n-1
与n
本身同属于一个集合,而类似这样的集合,我们若得到其最终的大小,其中最大的就是我们所需要的最长连续区间。
那么如何得到这些集合呢?这里通过维护一个区间的两端来聚合所有可以连接这个区间的值。因为任何一个值n
想要连接上某个连续区间,其n-1
或n+1
势必是这个连续区间的某端,所以核心思路是我们只需要维护一个连续区间两端,将其映射到的其所属的区间的长度,便可以每次都得到连续区间扩展后的长度。
以下是Java的题解代码实现。
以下是第二种Java的题解代码。这个代码的主要思路是找到每个连续区间的最小值,然后从最小值开始每次自增然后判断当前值是否在给定的数里存在,若存在则继续自增查找,直到不存在为止,此时就可以得到连续区间的长度。
这里的第二个循环看似是嵌套的两层循环,但实际上每个集合中的元素最多访问一次,所以实际时间复杂度是O(n)的。
以下是C++的题解代码实现。