首页 > 其他分享 >leetcode_128_最长连续序列解析

leetcode_128_最长连续序列解析

时间:2024-08-29 16:22:24浏览次数:14  
标签:200 numSet nums 序列 num 开头 128 解析 leetcode

题目

给定一个未排序的整数数组 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

解析

问题需要被分解为几个子问题:

如何确定一个数是连续序列的起点?

如何高效地扩展连续序列?

如何跟踪和更新最长序列的长度?

解题思路:

用哈希表查找这个数前面一个数是否存在,即num-1在序列中是否存在。存在那这个数肯定不是开头,直接跳过。
因此只需要对每个开头的数进行循环,直到这个序列不再连续。 以题解中的序列举例:
[100,4,200,1,3,4,2]
去重后的哈希序列为:
[100,4,200,1,3,2]
按照上面逻辑进行判断:
元素100是开头,因为没有99,且以100开头的序列长度为1
元素4不是开头,因为有3存在,过,
元素200是开头,因为没有199,且以200开头的序列长度为1
元素1是开头,因为没有0,且以1开头的序列长度为4,因为依次累加,2,3,4都存在。
元素3不是开头,因为2存在,过,
元素2不是开头,因为1存在,过。

代码

func longestConsecutive(nums []int) int {
    numSet := map[int]bool{}
    for _, num := range nums {
        numSet[num] = true
    }
    longestStreak := 0
    for num := range numSet {
        if !numSet[num-1] {
            currentNum := num
            currentStreak := 1
            for numSet[currentNum+1] {
                currentNum++
                currentStreak++
            }
            if longestStreak < currentStreak {
                longestStreak = currentStreak
            }
        }
    }
    return longestStreak
}

标签:200,numSet,nums,序列,num,开头,128,解析,leetcode
From: https://blog.csdn.net/shulu/article/details/141681939

相关文章

  • leecode_049_字母异位词分组解析
    题目给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],[&......
  • 435. 无重叠区间(leetcode)
    https://leetcode.cn/problems/non-overlapping-intervals/description/贪心:思路是更新重叠的区间classSolution{publicinteraseOverlapIntervals(int[][]intervals){//区间问题,首先排序,找到发生重叠的两个区间,将右边的重叠区间移除,实际对应代码的操......
  • Dapper传递参数对象时,只支持属性,无法解析字段(出现Parameter '?id' must be defined)
    有的时候使用Dapper执行数据操作时,我们会把模型对象直接作为参数传递进去,但是需要在注意的是!Dapper解析数据是根据属性进行解析的,如果传递的类中使用字段赋值,就会报错 Parameter'?xxx'mustbedefinedclassAAA{publicintID{get;set;}......
  • 452. 用最少数量的箭引爆气球(leetcode)
    https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/思路是排序,方便计算气球重叠,难点是在重叠时更新右边界,更新为两个区间的最右重合点,因为这个点是最少一支箭就可以射掉两个气球的最右点,再去下个循环判断区间重合classSolution{......
  • Android开发 - Serializable 接口对对象进行“打包”传递和接收后“解包”解析
    Serializable是什么Serializable是一种接口,用于将对象转换成字节流。通俗地说,Serializable是一种让对象能够“打包”和“解包”的方式,使得它们可以在存储和传输时保留其状态和数据Serializable的好处在程序中,我们经常需要在不同地方传递数据,比如在两个Activity之间传......
  • Android开发 - “序列化”与“反序列化”解析
    简介序列化和反序列化是计算机科学中两个非常常用的概念。简单来说,它们是将数据转换成不同形式的过程序列化(Serialization)序列化是将对象(比如一个Java对象或一个Python字典)转换成一种可以保存或传输的格式的过程。这种格式通常是字节流或字符串。通过序列化,你可以将一个......
  • LeetCode-Python-1539. 第 k 个缺失的正整数(二分)
    给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。请你找到这个数组里第 k 个缺失的正整数。示例1:输入:arr=[2,3,4,7,11],k=5输出:9解释:缺失的正整数包括[1,5,6,8,9,10,12,13,...]。第5个缺失的正整数为9。示例2:输入:arr=[1,2,3,4],k=2......
  • 【性能优化】:设计模式与技术方案解析(二)
    引言在【性能优化】:探索系统瓶颈的根源(一)文章中,我们已经分析了手动结算的弊端和瓶颈,本文来分析下怎么优化系统性能。需求分析既然手动结算耗时费力易出错,那么能不能开发一个**程序自动化处理**呢?如果要开发一个自动化跑批的程序,核心功能点是什么呢?第一:需要能正常运行;......
  • 非结构化文档解析
    参考:RAG效果优化:高质量文档解析详解知识库RAG的核心之一就是知识库的离线存储,如何将非结构化文档存储是非常重要的。PDF和Word文件结构word文件解析pdf文件解析Papermage介绍总结阿里云上的文件解析方法示例准确率参考......
  • Android开发 - Parcel 类打包对象数据进行传递解析
    Parcel是什么Parcel是用于对象序列化和反序列化的一个类。通俗地说,它是一种轻量级的容器,常用于打包对象的数据(如基本类型和其他Parcelable对象),使它们能够在不同的组件(如Activity、Service等)之间传递Parcel的主要作用不同的组件(如Activity、Service)之间需要传递数据。......