(哈希查找)leetcode128. 最长连续序列
文章目录
- 一、题目
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、本题小知识
一、题目
1、题目描述
给定一个未排序的整数数组 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
2、基础框架
- C++版本给出的基础框架如下:
3、原题链接
https://leetcode.cn/problems/longest-consecutive-sequence/
二、解题报告
1、思路分析
(1)(1)(1)首先对数组去重,然后遍历去重后的数组,遍历元素为num时,查找数组中是否存在num+1, num+2…。如果一直找到num+x,而num+x+1不存在时,则以num为起点的连续序列长度为x+1。
(2)(2)(2)如果每个元素都当作起点查找的话,会有很多重复。比如数组中存在num-1,那么num,num+1…都是属于以num-1为起点的序列的,没必要从num,num+1…等为起点计数。
(3)(3)(3)所以,判断元素num是否可以作为起点,只要判断数组中是否存在num-1。不存在的话就可以作为起点。
(4)(4)(4)为了降低查找的时间复杂度,需要用哈希表存储数组。哈希表查找的时间复杂度为O(1).
2、时间复杂度
时间复杂度为O(n),空间复杂度为O(n)
3、代码详解
class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int ans = 0;for (Integer num: set){int cur = 0;if (!set.contains(num-1)) {cur++;while(set.contains(num+1)) {cur++;num++;}ans = Math.max(ans, cur); }}return ans;}
}
三、本题小知识
1.java中Set的使用
添加元素:set.add()
查找元素是否存在:set.contains(value)
遍历set:for(T val : set)
相关文章:
(哈希查找)leetcode128. 最长连续序列
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识一、题目 1、题目描述 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。…...
js中splice方法和slice方法
splice方法用来操作数组splice(startIndex,deleteNum,item1,....,)此操作会改变原数组。删除数组中元素参数解释:startIndex为起始index索引。deleteNum为从startIndex索引位置开始需要删除的个数。分三种情况:没有传第三个参数的情况下,dele…...
c++ argparse
需求 c程序传参数,像python中argparse一样方便。 方法1 用gflags 参考https://heroacool.blog.csdn.net/?typeblog git clone https://github.com/gflags/gflags cd gflags # 进入项目文件夹 cmake . # 使用 cmake 编译生成 Makefile 文件 make -j 24 # make 编…...
内大892复试真题16年
内大892复试真题16年 1. 输出三个数中较大数2. 求两个数最大公约数与最小公倍数3. 统计字符串中得字符个数4. 输出菱形5. 迭代法求平方根6. 处理字符串(逆序、进制转换)7. 寻找中位数8. 输入十进制输出n进制1. 输出三个数中较大数 问题 代码 #include <iostream>usin…...
面试题 05.02. 二进制数转字符串
二进制数转字符串。给定一个介于0和1之间的实数(如0.72),类型为double,打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示,则打印“ERROR”。 示例1: 输入:0.625输出:"0…...
MySQL数据更新操作
文章目录前言添加数据插入数据删除数据修改数据前言 提示:这里可以添加本文要记录的大概内容: 数据更新有两种办法: 1:使用数据可视化工具操作 2:SQL语句 添加数据 前面的添加数据命令一次只能插入一条记录。如果想…...
C# 封装
修正bug之前总是要考虑是什么导致了这个bug,并花些时间了解发生了什么。增加打印输出行的语句可能是一个很有效的调试工具。增加语句来打印诊断信息时,要使用Debug.WriteLine。构造器是CLR第一次创建一个新对象实例时调用的方法。字符串插值会让字符串拼…...
每日学术速递3.2
CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.Interactive Segmentation as Gaussian Process Classification(CVPR 2023) 标题:作为高斯过程分类的交互式分割 作者:Minghao Zhou, Hong Wang, Qian Zha…...
PCBA方案设计——LCD体重电子秤方案
体重秤,一种测量体重的电子秤,与最近很火的体脂秤来比来说,他是的功能能就有点单一了,只能测量体重,而体脂秤可以精准抓取测量体脂体重等一系列的数据,功能更为多样,但相比之下体重秤的功能简单…...
动态规划--背包问题
动态规划背包问题算法思路代码实现背包问题 假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要: 水(重3磅,价值10) 书&…...
从0开始学python -45
Python3 正则表达式 -3 正则表达式对象 re.RegexObject re.compile() 返回 RegexObject 对象。 re.MatchObject group() 返回被 RE 匹配的字符串。 start() 返回匹配开始的位置end() 返回匹配结束的位置span() 返回一个元组包含匹配 (开始,结束) 的位置 正则表达式修饰符…...
如何用BurpSuite抓取手机数据包
文章目录前言准备工具Burp Suite物理机或虚拟机(移动设备)手机抓包网络环境开启burp并设置代理手机配置代理安装Burp证书开始抓包踩坑后记前言 最近挖了一波src,挖来挖去发现有很多公众号或者app没有测试,这就需要Burp能够抓取手机的数据包了࿰…...
Linux性能监控工具iostat解析
1.iostat命令详解 CPU 内存 磁盘 网络 四大子系统 1.1 查看提供iostat命令的软件包 yum provides "*/iostat" yum -y install systatiostat 1 显示实时的数据 iostat 结果自系统启动以来的平均值1.2 iostat命令CPU指标 %user 应用程序消耗CPU资源占比 %nice 进…...
3D可视化大屏制作真的那么难?没有好用的软件解决吗?
有多少人印象里的数据可视化大屏还是像这样的二维大屏?这种二维可视化大屏早就不能满足审美日益提高的大众了。 现在用的都是3D可视化大屏,这种结合了3D技术的可视化形式不仅让数据更加的清晰,也增加了美感,这观看体验ÿ…...
C语言|文件读写,代码运行后留下“记忆”
前言对于一个代码,运行时可能需要保留产生的结果,例如计算值,筛选值,记录点或者小游戏的得分,而正常情况下我们要保存一个数据,想到的肯定是打开我们的文本软件,手撸文字,今天这篇文…...
【2023unity游戏制作-mango的冒险】-6.关卡设计
👨💻个人主页:元宇宙-秩沅 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 秩沅 原创 收录于专栏:unity游戏制作 ⭐mango的冒险关卡设计⭐ 文章目录⭐mango的冒险关卡设计⭐👨&#…...
JavaScript高级 浏览器WebStorage
WebStorage主要提供了一种机制,可以让浏览器提供一种比cookie更直观的key、value存储方式: localStorage:本地存储,提供的是一种永久性的存储方法,在关闭掉网页重新打开时,存储的内容依然保留; …...
$ 3 :类型强制转换场景、printf函数
1、类型强制转换场景 #include <stdio.h> //强制类型转换 int main() {int i=5;float j=i/2;float k=(float)i/2;printf("%f\n",j);printf("%fln",k);return 0;} j得到的值为2,k得到的值是2.5,因为当我们整数做除法时,默认进行整除,要得到小数,…...
视频会议系统异常中断故障分析案例
1. 背景 某电气化局的用户反馈,近期视频系统在使用过程中出现频繁中断的情况,这种情况影响到用户的视频体验和工作效率。 针对此问题,我们将NetInside流量分析系统部署到电气化局机房,使用流量分析系统提供实时和历史原始流量。…...
什么是文件传输中台?
企业文件传输的场景有哪些? 企业日常办公中无时无刻不在产生数据文件。多样化的数据已成为企业的重要资产,更被称为是“新石油”。数据并不是单单存储起来就行了,而是需要高效又安全的让数据流转起来,释放其自身的价值࿰…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
