当前位置: 首页 > news >正文

[python 刷题] 128 Longest Consecutive Sequence

[python 刷题] 128 Longest Consecutive Sequence

题目:

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

这题给了一个没有排序的数组,并且要求找出最长的连续序列

最简单的方式其实还是排序,不过题目中要求时间复杂度为 O ( n ) O(n) O(n),而排序的时间复杂度为 O ( n l o g ( n ) ) O(n log(n)) O(nlog(n))

Union Find 也可以用来解这题,它的时间复杂度是 amortized linear,不过这个问题的话有一个 linear 的解。

[100,4,200,1,3,2] 为例,假设有一个无限延长的 x 轴,所有的点在 x 轴上看起来是这个样子的:

在这里插入图片描述

这个情况下就比较清楚的可以看到哪个点在哪个 cluster 里,在实际的实现中,可以用一个 set 去存储所有出现的值,每次将值存入 cluster 中,都可以检查一下当前值是否是 cluster 的最小值,如果是的话,查看当前 cluster 的长度

代码如下:

class Solution:def longestConsecutive(self, nums: List[int]) -> int:num_set = set(nums)max_len = 0for num in num_set:if (num - 1) in num_set:continuelocal_max = 1right = num + 1while right in num_set:local_max += 1right += 1max_len = max(max_len, local_max)return max_len

整体时间复杂度的分析:

创建 set 的时间复杂度为 O ( n ) O(n) O(n)

第一个 for 循环的时间复杂度为 O ( n ) O(n) O(n)

查询当前值是否存在与 set 的时间复杂度为 O ( 1 ) O(1) O(1)

第二个循环 while 在最差的情况下会跑 O ( n ) O(n) O(n) 次,但是因为有 if,的检查,所以这个情况最坏只会跑一次,而 O ( n + n ) O(n + n) O(n+n) 在大 O 里面依旧是 O ( n ) O(n) O(n),所以整体的时间复杂度为 O ( n ) O(n) O(n)

http://www.lryc.cn/news/171513.html

相关文章:

  • SpringMVC之JSON数据返回与异常处理机制
  • 【第四阶段】kotlin语言的定义类和field关键字学习
  • OpenResty使用漏桶算法实现限流
  • Activiti源码跟踪之模型Model操作
  • C#-WinForm-发送邮件
  • Springboot整合jdbc和Mybatis
  • 日常生活中的常用命令及操作
  • 【C++杂货铺】国庆中秋特辑——多态由浅入深详细总结
  • MongoDB基础详解
  • 解锁前端Vue3宝藏级资料 第五章 Vue 组件应用 4 ( provide 和 inject )
  • 【List篇】LinkedList 详解
  • 推动统一供应链“度量衡”,上汽大通突破传统拥抱SaaS生态
  • 蓝牙核心规范(V5.4)10.9-BLE 入门笔记之GAP
  • nginx 配置 ssl
  • 家居设计软件Live Home 3D Pro mac中文版特点介绍
  • OkHttp - 现代应用网络的方式
  • SpringBoot3基础:最简项目示例
  • flex:1详解,以及flex:1和flex:auto的区别
  • 在VMware虚拟机中固定CentOS系统ip(使用桥接模式)
  • 怎样才能让百度搜索到自己的博客?--九五小庞
  • 【学习笔记】多模态综述
  • MLAgents (0) Unity 安装及运行
  • typename关键字详解(消除歧义)
  • 设计模式_解释器模式
  • 【算法基础】数学知识
  • PDCA循环
  • Redis 缓存雪崩、缓存穿透、缓存击穿
  • Android Media3 ExoPlayer 开启缓存功能
  • MyBatis注解开发
  • C# Onnx Yolov8 Cls 分类