数组中的最长连续子序列

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

热度指数：37816 时间限制：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]

输出

备注:

算法知识视频讲解

JavaScript Node

♈FourBrother✅已认证♉

function MLS( arr ) {
    // write code here
    const newArr = [...new Set(arr)].sort((a, b) => a - b)
    let max = 0
    let point = -1
    let pre = Infinity
    newArr.forEach((item, index) => {
        if (point === -1) {
            max = 1
            point = 0
        } else {
            if (item === pre + 1) {
                max = Math.max(max, index - point + 1)
            } else {
                point = index
            }
        }
        pre = item
    })
    return max
}

发表于 2021-11-19 16:39:03 回复(0)