LC 128.最长连续序列

news/2024/9/22 16:44:26/

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/news/1501233.html

相关文章

2.6基本算法之动态规划8464:股票买卖

描述 最近越来越多的人都投身股市&#xff0c;阿福也有点心动了。谨记着“股市有风险&#xff0c;入市需谨慎”&#xff0c;阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某只股票在未来 N 天的价格&#xff0c;他希望买卖两次&#xff0c;使得获得的…

富唯智能转运机器人:高效、智能、未来的选择

在现代工业中&#xff0c;高效的物流和物料处理是提升生产效率的关键。富唯智能转运机器人&#xff0c;以其卓越的技术和智能化的设计&#xff0c;为各行业提供了完美的解决方案。 产品概述 富唯智能转运机器人搭载ICD系列核心控制器&#xff0c;拥有多种移载平台&#xff0c…

PVE环境中调整虚拟机磁盘大小

我的希望将PVE中的虚拟机磁盘调整一下&#xff0c;增加20GB。在查询了一些资料后&#xff0c;做一下总结教程。 环境是 PVE8.2.2 版本&#xff0c;虚拟机系统是centos7.9.2009-minimal&#xff0c; 安装系统时划分磁盘分区方式是默认分区方式&#xff08;不同分区方式下&#…

【c++刷题笔记-单调栈】day49: 42. 接雨水 、84.柱状图中最大的矩形

42. 接雨水 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a;单调栈&#xff0c;第一个是比栈顶大的是右边界&#xff0c;栈顶元素是底&#xff0c;出栈后下一个栈顶元素是左边界。 使用左右边界最小值与中间元素相减算出高度&#xff0c;右边界减左边界减1算出宽度…

C#初级——条件判断语句、循环语句和运算符

条件判断语句 简单的条件判断语句&#xff0c;if()里面进行条件判断&#xff0c;如果条件判断正确就执行语句块1&#xff0c;如果不符合就执行语句块2。 if (条件判断) { 语句块1 } else { 语句块2 } int age 18;if (age < 18){Console.WriteLine("未…

C# 代理模式

栏目总目录 概念 代理模式是一种结构型设计模式&#xff0c;它为其他对象提供一种代理以控制对这个对象的访问。在代理模式中&#xff0c;我们创建一个具有现有对象&#xff08;称为“真实对象”或“被代理对象”&#xff09;相同功能的代理对象。代理对象可以在客户端和目标对…

windows下实现mongodb备份还原

添加环境变量 把mongodb安装目录下的bin路径添加到环境变量的path路径: 备份库 打开CMD&#xff0c;执行以下命令&#xff1a; mongodump -u test -p test -d test -o D://backup_mongodb//20220706 –gzip 参数说明&#xff1a; -u 用户名 -p 密码 -d 需要备份的库名称…

FPGA开发——偶数分频器的设计

一、概述 1、我们在日常进行FPGA的开发之中&#xff0c;会根据需求的不同设计不同的功能实现&#xff0c;这就需要不同的分频信号&#xff0c;而分频的思想在我们的日常开发中显得尤为重要。用通俗易懂的说法表示分频就是对计数器进行一个进一步设计从而达到不同的分频器的思想…