LeetCode 128 Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
**Input:** [100, 4, 200, 1, 3, 2] **Output:** 4 **Explanation:** The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.
题目大意:
给出一个未排序的整数数组,找出最长的连续元素序列的长度。
如: 给出[100, 4, 200, 1, 3, 2],最长的连续元素序列是[1, 2, 3, 4]。返回它的长度:4。
解题思路:
这是连通问题,如果用排序方法,很容易,但时间复杂度为O(nlogn)。考虑改进,因为连通集,容易想到HashMap,把每个元素加入到其中,
然后对每个元素进行相邻查找。相邻查找就是以此元素为中心,向上向下在Map查找,从而得到此元素的最大连续序列长度。查找过的元素
在Map中删除,以免重复计算。
注意事项:
- 加入set之后的元素不能再内循环中删除,因为外循环是遍历每一个数,可能会遍历到删除的数,正确做法是用map的value来记录是否访问过。
Python代码:
1 | def longestConsecutive(self, nums: List[int]) -> int: |
注意事项:
- Java中在for循环中不能修改hashSet,所以只能用HashMap且value存boolean替代。HashMap表示此Map还是否含有该元素。
Java代码:
1 | public int longestConsecutive(int[] nums) { |
算法分析:
时间复杂度为O(n)
,空间复杂度O(n)
。