LeetCode OJ - Longest Consecutive Sequence
时间:2022-04-14 16:44
这道题中要求时间复杂度为O(n),首先我们可以知道的是,如果先对数组排序再计算其最长连续序列的时间复杂度是O(nlogn),所以不能用排序的方法。我一开始想是不是应该用动态规划来解,发现其并不符合动态规划的特征。最后采用类似于LRU_Cache中出现的数据结构(集快速查询和顺序遍历两大优点于一身)来解决问题。具体来说其数据结构是HashMap
总体思路是,顺序遍历输入的数组元素,对每个元素先看下HashMap的key中是否已经有这个元素,如果有则无需做任何事情,如果有,再看下这个元素的左邻居也就是比它小1的元素是否在,如果在的话把左邻居的LNodel的next指针指到当前这个元素的LNode,然后再看右邻居的元素是否存在hashmap中,如果在,则把当前指针的next指到右邻居节点上,通过反复这样的操作,最后所有连续的sequece的LNode都被连在一起。
之后再计算哪个连续的链表长度最长。
下面是AC代码:
LeetCode OJ - Longest Consecutive Sequence,布布扣,bubuko.com