Leetcode之Longest Consecutive Sequence 问题
问题描述:
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.
问题来源:Longest Consecutive Sequence (详细地址:https://leetcode.com/problems/longest-consecutive-sequence/description/)
思路分析:
题目要求的是时间复杂度为O(n),可想而知我们必须要牺牲空间复杂度了,简单点我们就采用hashmap,key用来存放数组中的元素,value存放它所参与的最长序列。所以,简单的思路就是,当遍历到数组中每一个数组的时候,我们需要考虑他们邻近的情况(分左边和右边),然后合并起来(左边的加右边的,再加上自己)不就得到该数参与的最长的序列了吗?最后,我们取一下全局最大值就可以得到最终的结果了啊!当然我们是需要将三个值(左边的,自己和右边的)存起来的,以便下一次使用。最后,采用hashmap还有一个好处就是可以过滤掉数组中重复的数字。下面看一下代码就知道啥意思了.
代码: