首页 > 其他分享 >Leetcode Hot 100 & 128. Longest Consecutive Sequence

Leetcode Hot 100 & 128. Longest Consecutive Sequence

时间:2023-06-09 16:24:54浏览次数:72  
标签:set Sequence nums len current Hot num Longest 遍历

  参考资料:

  考点:哈希 & [题干]

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

  做的时候冥思苦想了半天,因为这个题目要求是O(n)的解法,后来看到题解的时候还一度怀疑官方解法达不到O(n)。

  1. 心路历程

  首先,列表中可能有重复元素,但在结果里是不会显示出来的,因此首先把nums列表转换成set这个没问题。然后,需要寻找最长序列,不遍历一遍是肯定达不到的。但是题干也给了提示O(n),也就是说基本上让你遍历一遍就把结果找到,这就很难了。。

  比如一个列表[3, 1, 2, 4],我们遍历到 3 的时候,需要判断它前面一个整数2和后面一个整数4是否同样在列表中,这个判断的时间可以在O(1)中完成吗?我想破头也没想出来,但实际上,使用集合的in操作是可以实现的。这里可以参考这个文章:https://www.jianshu.com/p/a8fa3d31aa40,里面列举了常见数据结构基本操作的时间复杂度。而集合的in操作就是O(1)的,因为内部使用了hash表。值得注意的是,这篇文章同样提到了set的内部实现是dict,因此dict的查找也是O(1),看来dict的功能比集合要强一些呀~ 其实,想到使用集合in操作这个判据,后面的就水到渠成了,对于上面这个例子,如果当前遍历到3,首先查看3 - 1 = 2在集合里,则直接跳过,只有当遍历到1的时候,发现0没有在集合里,就向后遍历,一直发现 1 2 3 4都在,则最大长度是4。写出的代码如下:

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_set = set(nums)
        max_len = 0

        for num in num_set:
            if num - 1 not in num_set:
                current_len = 1
                current_num = num
                while current_num + 1 in num_set:
                    current_len += 1
                    current_num = current_num + 1
                    
                max_len = max(max_len, current_len)

        return max_len

标签:set,Sequence,nums,len,current,Hot,num,Longest,遍历
From: https://www.cnblogs.com/chester-cs/p/17469510.html

相关文章

  • Atcoder ABC221G Jumping sequence
    发现这个\((x,y)\)对应的是曼哈顿距离不太好求,那直接逆时针旋转\(45\)度(其实应该还要伸长\(\sqrt{2}\)倍,但是可以当做\(d_i\)也伸长\(\sqrt{2}\)倍不用去管)转化成切比雪夫距离\((x-y,x+y)\)。同时对应的\(4\)个方向在旋转后对应的方向也得到了改变:\(U(-d,d),......
  • 1502. Can Make Arithmetic Progression From Sequence
    /***1502.CanMakeArithmeticProgressionFromSequence*https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/description/*Asequenceofnumbersiscalledanarithmeticprogressionifthedifferencebetweenanytwoconsecut......
  • Photoshop 2023 v24.6 Beta 直装爱国版本ps
    win用户看这PsBeta最新直装版本已更新教程免破解。https://www.88appp.com/10714.htmlMac用户看这PsBeta最新直装版本已更新教程免破解。https://www.88appp.com/10742.html注意问题常见问题星球会更新https://t.zsxq.com/0eCxJEDoI......
  • PHOTOSHOP精简教程
    PHOTOSHOP(3.13开课)一、在启动时按Ctrl+Alt+Shift可以让PS恢复到默认的设置(PSD)●二、Adobe:美国奥多比公司三、文件的新建1、文件\新建(Ctrl+N)2、按住Ctrl键加上鼠标在工作区双击●3、1英寸=2.54cm    1英尺=30.5cm●四、图片的格式:jpg、bmp、gif、tiff注:gif格式支持透明与动态,......
  • ORA-01555:snapshot too old: rollback segment number X with name "XXXX" too small
    ORA-01555:snapshottooold:rollbacksegmentnumberXwithname"XXXX"toosmall在查询快照的时候select*fromtesttableasoftimestampto_timestamp('2023-04-0322:00:00','yyyy-mm-ddhh24:mi:ss')提示错误ORA-01555:snapshottooold:r......
  • CF1838E - Count Supersequences
    先考虑正着做,我们只考虑整个\(b\)序列中出现的第一个子序列\(a\)。这样,我们就是要往\(a\)中插入\(m-n\)个数,其中\(a_{i-1}\)和\(a_i\)之间不能有\(a_i\)(否则就会有更靠前的子序列)。\(a_1\)前面不能有\(a_1\),\(a_n\)后面什么都可以有。我们发现,我们可以先枚举\(a......
  • Linux的I/O复用之epoll:EPOLLONESHOT事件
        即使我们使用ET模式,一个socket上的某个事件还是可能被触发多次,这在并发程序中就会引起一个问题,比如一个线程在读取某个socket上的数据后开始处理这些数据,而在数据的处理过程中该socket上又有新的数据可读,此时另外一个线程被唤醒来读取这些新的数据,于是就出现两个线程同......
  • photoprism+rclone搭建
    vps空间小,所以使用onedrive为例作为存储来搭建photoprism主要分为以下几步:使用rclone挂载onedrive部署photoprism获得rclone.conf首先在本地电脑上安装rclone然后运行rcloneconfig参照https://rclone.org/onedrive/进行远程配置然后配置完成后,~/.config/rclone/rcl......
  • Photoshop 2023 (ps2023) Mac/win最新版
    Photoshop2023(简称ps2023)是Adobe推出的Mac版本图像处理软件。它是业内最为知名的、功能最为强大的图像编辑软件之一,被广泛应用于平面设计、网页设计、摄影后期处理等方面。→→↓↓载Photoshop2023mac/win版 在Photoshop2023中,用户可以使用丰富多彩的工具和特效,对图片进......
  • Photoshop 2023 Beta(PS2023Beta) v24.6 AI测试版 win/ mac版
    Photoshop2023Beta内置Ai绘图功能版,这是世界上第一个创意和设计工作流程的副驾驶,为用户提供了一种神奇的新工作方式。这将两个强大的成像引擎结合在一起——Photoshop和生成式AI,使您能够通过文本提示从Photoshop内部生成内容,并使用Photoshop的全面工具对其进行编辑以创建非凡的结......