LeetCode 128 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.
一句话题意
给定一个未排序的整数数组,找出(排序后)数组里面最长的连续元素序列(如[2, 3, 4, 5]
)的长度
解题思路
简单粗暴的做法就是排序后扫一遍统计长度,当然是O(NlogN)排序之后O(N)扫一遍统计长度,这样总体复杂度是O(NlogN),然而题目要求O(N),不然会超时。
维护当前已经组成的所有连续序列,每次将一个数组中的元素加入已有序列并更新当前的所有连续序列。扫描一遍原数组需要O(N),维护过程使用哈希表做到O(1),实现总体O(N)的复杂度。
读入一个数 x ,我们在HashMap中寻找其左边,其右边是否存在,存在的话返回其长度,不存在则置0
当前数的位置的长度,就是上一步中找到的两个长度的和再加1.
同时需要找到当前位置,最左边的边界和最右边的边界,根据刚刚得到的长度就可以计算出来,然后更新其值为上一步计算得到的值。
另外,考虑到性能,可以用unordered_set实现哈希表。
0 条评论