我要招人

去企业版

首页 > 试题广场 >

数组中的最长连续子序列

[编程题]数组中的最长连续子序列

热度指数：36175 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

数据范围： $1 \le n \le 10^5$ ，数组中的值满足 $1\le val \le 10^8$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

输入

[100,4,200,1,3,2]

输出

示例2

输入

[1,1,1]

输出

备注:

算法知识视频讲解

Python3

刘洁o

# @param arr int整型一维数组 the array

# @return int整型

class Solution:

def MLS(self , arr: List[int]) -> int:

# write code here

arr=sorted(arr)

dp=[1]*len(arr)

i=1

res_l=[arr[0]]

res=1

while i<len(arr):

if arr[i]==res_l[-1]+1:

res_l.append(arr[i])

res=max(len(res_l),res)

elif arr[i]==res_l[-1]:

res=max(len(res_l),res)

else:

res_l=[arr[i]]

i=i+1

return res

发表于 2023-01-09 18:04:02 回复(0)

Python3

梦幻泡影oO

标准的滑动窗口写法

class Solution:
    def MLS(self , arr: List[int]) -> int:
        N = len(arr)
        arr.sort()

        def check(l, r, rep):  # O(1) 判断是否连续
            return l < r and arr[r] - arr[l] != r - l - rep

        l, r = 0, 0
        rep = 0
        ret = 0
        while r < N:
            while check(l, r, rep):  # 当不满足时，右移 l
                if l + 1 < N and arr[l] == arr[l + 1]:
                    rep -= 1
                l += 1

            ret = max(ret, r - l + 1 - rep)
            if r + 1 < N and arr[r] == arr[r + 1]:
                rep += 1
            r += 1

        return ret

发表于 2022-03-24 12:45:44 回复(0)

Python3

JSFaner

class Solution:
    def MLS(self , arr: List[int]) -> int:
        if not arr: return 0
        arr.sort()
        n = len(arr)
        cnt,res = 1,1
        for i in range(1,n):
            if arr[i] == arr[i-1]: continue
            if arr[i] == arr[i-1] + 1: cnt += 1
            else: cnt = 1
            res = max(res,cnt)
        return res

发表于 2021-12-25 18:16:14 回复(0)

Python3

Jackson_X

class Solution:
    def MLS(self , arr ):
        # write code here
        arr = sorted(arr)
        ans = 1
        tmp = 1
        for i in range(1, len(arr)):
            if arr[i] == arr[i-1]:
                continue
            if arr[i] == arr[i-1]+1:
                tmp +=1
            else:
                ans = max(ans, tmp)
                tmp = 1

        return max(ans, tmp)

发表于 2021-10-27 23:27:00 回复(0)

Python3

光明20190828114684

class Solution:
    def MLS(self , arr ):
        # write code here
        # 对数组去重
        arr_set = set(arr)
        ans = 0
        for i in range(len(arr)):
            # 寻找多个连续子序列中最小值
            if arr[i] -1 in arr_set:
                continue
            start = arr[i]
            while start in arr_set:
                start += 1
                # 比较每个连续子序列的长度
                ans = max(ans, start - arr[i])
        return ans

发表于 2021-08-02 21:02:30 回复(0)