Leecode热题100---128：最长连续数列

题目：
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

1、C++

#include 
#include 
#include 
using namespace std;

int longestConsecutive(vector<int>& nums)
{
	if (nums.size() == 0)
		return 0;
	// vector数组升序排序
	sort(nums.begin(), nums.end());
	// 初始化最长连续序列长度为1，当前连续序列长度pcnt为1
	int cnt = 1, pcnt = 1;
	for (int i = 1; i<nums.size(); i++)
	{
		if (nums[i] - nums[i - 1] == 1)
			pcnt++;
		else if (nums[i] - nums[i - 1] > 1)
		{
			if (pcnt>cnt)
				cnt = pcnt;
			pcnt = 1;
		}
	}
	// 末尾判断是否需要更新局部变量值
	return pcnt>cnt ? pcnt : cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2、python

import cv2
import numpy as np

class Solution:
    def Longest(self,nums:List[int]) -> int:
        # 构建 set，去重，建立一个List集合，用来存放去重后的元素
        set_nums = set(nums)
        # 初始化一个最大长度变量，用于后续更新
        len_max = 0

        for num in set_nums:
            # 如果 num - 1 不在 set_nums 中，那 current num 可以作为连续子序列的首部
            if num-1 not in set_nums:
                len_seq = 1;

                # 如果 num + 1 不在 set_nums 中，那就达到了连续子序列的尾巴
                while num+1 in set_nums:  # 以 current num 进行枚举
                    len_seq +=1
                    num += 1
                # 更新最大长度变量
                len_max = max(len_max,len_seq)
        return len_max
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22