LC 128.最长连续序列

devtools/2024/12/22 20:20:27/

leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">128.最长连续序列

给定一个未排序的整数数组 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 ≤ n u m s . l e n g t h ≤ 1 0 5 0 \leq nums.length \leq 10^5 0nums.length105
  • − 10 9 ≤ n u m s [ i ] ≤ 1 0 9 {-10}^9 \leq nums[i] \leq 10^9 109nums[i]109

解法一(排序)

思路分析:

  1. 题目要求:找出数字连续的最长序列,且不需要在原数组中连续,则可以尝试对原数组进行排序;
  2. 排序之后,在遍历数组,判断 相邻元素是否连续, 若连续则计数长度+1, 若不连续则将计数长度归1,重新开始计数;
  3. 因为序列长度,需要算上第一个元素,即 只有一个元素时, 序列长度为1, 所以初始序列长度为 1;
  4. 同时需要注意: 题目并未说明数组中的元素不重复, 所以需要排除重复元素的情况

实现代码如下:

java">class Solution {public int longestConsecutive(int[] nums) {int n = nums.length;if (n == 0) {return 0;}// 排序Arrays.sort(nums);// 最小连续序列长度为 1int max = 1;int flag = 1;for (int i = 0; i < n-1; ++ i) {if (nums[i] == nums[i+1] - 1) {// 若连续 则长度增加flag ++;} else if (nums[i] == nums[i+1]) {// 排除连续相等的元素continue;}else {// 不连续 则重新计数flag = 1;}// 时刻更新最长序列max = Math.max(flag, max);}return max;}
}

提交结果如下:

解答成功:

执行耗时:12 ms,击败了98.27% 的Java用户

内存消耗:55.3 MB,击败了95.98% 的Java用户

复杂度分析:

  • 时间复杂度: O ( n × l o g n ) O(n \times log n) O(n×logn), 对数组排序的复杂度;
  • 空间复杂度: O ( 1 ) O(1) O(1)

解法二(哈希表)

思路分析:

  1. 对数组中的每个数进行枚举, 然后再在数组中寻找x+1, x+2, x+3, …, 当匹配到x+y,即此时序列长度为y+1
  2. 但是每次遍历匹配的时间复杂度为 O ( n ) O(n) O(n),涉及到匹配的优化可以考虑使用哈希表来减少匹配的复杂度;即查看一个数是否存在的时间复杂度可以优化为 O ( 1 ) O(1) O(1)
  3. 所以只需要遍历数组元素,然后以每个元素为起点x,持续判断x+?是否存在,即可得到以x为起点的序列长度;
  4. 但是此时的时间复杂度依然为 O ( n 2 ) O(n^2) O(n2),每个元素可能会重复遍历多次, 比如序列[100,4,200,1,3,2]中,以2为起点和以1为起点都会导致重复遍历;
  5. 最优情况是: 只从每个序列的起点开始遍历获取序列长度,例如序列[100],序列长度为1,起点为100, 序列[1,2,3,4],只从起点1遍历一次,而不会再去从2开始遍历[2,3,4];
  6. 所以可以在遍历数组元素时,判断当前元素是否为序列的起点,若为序列起点,则开始匹配序列,并获取序列长度,若不是序列起点,则跳过;
  7. 判断一个元素x是否为序列起点, 可以判断哈希表中是否存在元素x-1,若存在,则说明序列可以从x-1开始,即x不是序列起点; 若不存在,则说明x为序列起点
  8. 同时,需要考虑数组元素的重复情况,以及哈希表的选取,因为不需要绑定数组元素的索引,即不需要使用Map来作为哈希表; 即使用Set作为哈希表即可,同时可以起到去重的作用;

实现代码如下:

java">class Solution {public int longestConsecutive(int[] nums) {// 定义哈希Set<Integer> set = new HashSet<>();// 遍历数组 并存入哈希表中去重for (int num : nums) {set.add(num);}// 最长序列长度int maxLen = 0;for (Integer num : set) {// 判断当前元素是否为序列起点if (!set.contains(num-1)) {// 为序列起点 遍历序列获取长度// 当前元素int currentNum = num;// 当前序列长度int currentLen = 1;while (set.contains(currentNum + 1)) {// 序列长度增加++ currentLen;++ currentNum;}maxLen = Math.max(maxLen, currentLen);}}return maxLen;}
}

提交结果如下:

解答成功:
执行耗时:27 ms,击败了59.27% 的Java用户
内存消耗:66.1 MB,击败了6.98% 的Java用户

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n),只需 O ( n ) O(n) O(n)的遍历数组元素;
  • 空间复杂度: O ( n ) O(n) O(n),需要使用哈希表来存储数组元素;

http://www.ppmy.cn/devtools/85390.html

相关文章

防火墙——网络环境支持

目录 网络环境支持 防火墙的组网 web连接上防火墙 web管理口 让防火墙接到网络环境中 ​编辑 管理员用户管理 缺省管理员 接口 配置一个普通接口 创建安全区域 路由模式 透明模式 混合模式 防火墙的安全策略 防火墙转发流程 与传统包过滤的区别 创建安全策略 …

【BUG】已解决:Downgrade the protobuf package to 3.20.x or lower.

Downgrade the protobuf package to 3.20.x or lower. 目录 Downgrade the protobuf package to 3.20.x or lower. 【常见模块错误】 【解决方案】 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身…

会员购项目面试题解析:高效数据抓取与异常处理

会员购项目 亮点 日志记录信息协程异步抓取数据&#xff0c;大大提高抓取速度捕获异常&#xff0c;并添加重试机制 源码 import logging import timeimport requests import asyncio import aiohttp from aiohttp import ContentTypeError import csv# 配置日志 logging.ba…

47、PHP实现机器人的运动范围

题目&#xff1a; PHP 实现机器人的运动范围 描述&#xff1a; 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动&#xff0c;每一次只能向左&#xff0c;右&#xff0c;上&#xff0c;下四个方向移动一格&#xff0c;但是不能进入行坐标和列坐标的数位之和大于k…

汽车免拆诊断案例 | 2018 款别克阅朗车蓄电池偶尔亏电

故障现象 一辆2018款别克阅朗车&#xff0c;搭载LI6发动机和GF6变速器&#xff0c;累计行驶里程约为9.6万km。车主反映&#xff0c;该车停放一晚后&#xff0c;蓄电池偶尔亏电。 故障诊断 接车后用虹科Pico汽车示波器和高精度电流钳&#xff08;30 A&#xff09;测量该车的寄…

计算机网络中的 IPv6 部署与转换

背景介绍 随着互联网的迅速发展&#xff0c;IPv4 地址资源日益枯竭&#xff0c;无法满足未来互联网设备连接的需求。为了解决这一问题&#xff0c;IPv6 应运而生。IPv6&#xff08;互联网协议第六版&#xff09;提供了比 IPv4 更大的地址空间、更好的安全性和扩展性。然而&…

爬虫自己做的

1.urllib 1.1基本使用 1.2 下载&#xff08;图片&#xff0c;页面&#xff0c;视频&#xff09; 1.3 get 1.3.1 quote 中文变成对应uncode编码 当url 的wd中文时 quote是将中文变成对应uncode编码 然后拼接成完整的url 1.3.2urlencode方法 wd有多个参数 1.3.3ajas get实例 …

【BUG】已解决:IndexError: positional indexers are out-of-bounds

IndexError: positional indexers are out-of-bounds 目录 IndexError: positional indexers are out-of-bounds 【常见模块错误】 【解决方案】 原因分析 解决方法 示例代码 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博…