最长连续序列(dp)

简介: 最长连续序列(dp)

题目

题目:最长连续序列


难度:中等


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


示例 1:


输入:nums = [100,4,200,1,3,2]

输出:4

解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。


示例 2:


输入:nums = [0,3,7,2,5,8,4,6,0,1]

输出:9


提示:0 <= nums.length <= 105

-109 <= nums[i] <= 109


题解:先排下序,用个一维dp数组,dp[n]记录长度,最后求出最大的dp值就行了,数组长度为0的先处理下就行了,注意点就是返回值默认值为1,先给dp数组都初始化为1,因为最小的连续长度肯定是包含自身也就是1


代码:


class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        //排序下
        Arrays.sort(nums);
        //max初始化为1,因为最小的连续序列长度为1,避免数组中只有一个元素的情况,也可以在上面写if提前过滤
        int max = 1;
        int[] dp = new int[nums.length];
        //先填充个初始长度,包括本身,也就是1
        Arrays.fill(dp,1);
        for(int i=1;i<nums.length;i++){
            //比前一个大,那么就是连续的
            if(nums[i]==nums[i-1]+1){
                dp[i] = dp[i-1] + 1;
            }
            //和前一个相等,连续长度保持就行
            if(nums[i]==nums[i-1]){
                dp[i] = dp[i-1];
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

每日单词

1.png


以上就是最长连续序列(dp)全部内容

相关文章
|
开发框架 监控 .NET
Visual Basic的Web服务和REST API开发指南
【4月更文挑战第27天】本文探讨了使用Visual Basic(VB.NET)构建Web服务和RESTful API的方法。首先介绍了Web服务的基础和REST API的概念,然后阐述了.NET Framework与.NET Core/.NET 5+对VB.NET的支持,以及ASP.NET Core在Web开发中的作用。接着,详细讲解了创建RESTful API的步骤,包括控制器与路由设置、模型绑定与验证,以及返回响应。此外,还讨论了安全措施、测试方法、部署选项和监控策略。最后强调,VB.NET开发者可以通过ASP.NET Core涉足现代Web服务开发,拓宽技术领域。
438 1
leetcode-1044:最长重复子串(滚动哈希)
leetcode-1044:最长重复子串(滚动哈希)
236 0
|
容器
【qt】下拉列表组件
【qt】下拉列表组件
191 0
|
11月前
|
存储 Python
Python中的多进程通信实践指南
Python中的多进程通信实践指南
166 0
|
Java Spring
异步编程 - 08 Spring框架中的异步执行_TaskExecutor接口和@Async应用篇2
异步编程 - 08 Spring框架中的异步执行_TaskExecutor接口和@Async应用篇2
261 0
|
设计模式 Java
"深入理解Java设计模式:探索工厂模式的实现与应用
"深入理解Java设计模式:探索工厂模式的实现与应用
|
安全 芯片
OVP过压保护芯片:为何电子工程师需要它?功能、作用全解析
OVP过压保护芯片:为何电子工程师需要它?功能、作用全解析
|
存储 机器学习/深度学习 设计模式
笔记 - 《领域驱动设计:软件复杂性应对之道》
笔记 - 《领域驱动设计:软件复杂性应对之道》
|
Kubernetes 网络协议 Linux
Cilium 系列 -13- 启用 XDP 加速及 Cilium 性能调优总结
Cilium 系列 -13- 启用 XDP 加速及 Cilium 性能调优总结