题目来源
Longest Consecutive Sequence
问题描述
给定一个未排序的整数数组,找出最长连续序列的长度。
例如,
给出 [100, 4, 200, 1, 3, 2],
这个最长的连续序列是 [1, 2, 3, 4]。返回所求长度: 4。
要求你的算法复杂度为 O(n)。
解决方案
Java
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (Integer n : nums)
set.add(n);
int res = 0;
int p = 0;
for(int data: nums) { //遍历原数组
p = 1;
set.remove(data);
for (int i = data-1; set.contains(i); i--) {
set.remove(i);
//移除hashset中已经求结果的数据(如[1,2,3]中的1,2,3的最大序列都是3),从而加快contains等函数
p++;
}
for (int i = data+1; set.contains(i); i++) {
set.remove(i);
p++;
}
res = res > p ? res : p;
}
return
python
class Solution:
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res=0
s=set(nums)
for i in nums:
data=i
p=1
for _ in range(len(s)):
if(data-1 in s):
p+=1
data-=1
s.remove(data)
data=i
for _ in range(len(s)):
if (data+1 in s):
p+=1
data+=1
s.remove(data)
res=max(res,p)
return
说明:在集合迭代过程中不允许对集合中的数据进行更改,比如python代码第三行中 for i in nums:
改为for i in s:
会报错RuntimeError: Set changed size during iteration
。