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

【力扣hot100】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 <= nums.length <= 105
-109 <= nums[i] <= 109


错误题解:

/*** @param {number[]} nums* @return {number}*/
var longestConsecutive = function(nums) {if(nums.length===0) return 0sort_nums=nums.sort(function(a,b){return a-b})let i = 0let arr_length=1let final_length=[]while(i<sort_nums.length){if(sort_nums[i]===sort_nums[i+1]-1){arr_length++i++}else{final_length.push(arr_length)arr_length=1i++}}final_length.sort(function (a, b) {return a - b})let result = final_lengthreturn result[result.length-1]
};

在这里插入图片描述
未处理当两个相同数字处在连续数字中间的情况,修改后:

/*** @param {number[]} nums* @return {number}*/
var longestConsecutive = function(nums) {if(nums.length===0) return 0sort_nums=nums.sort((a, b) => a - b )let i = 0let arr_length=1let final_length=[]while(i<sort_nums.length){if(sort_nums[i]===sort_nums[i+1]-1){arr_length++}else if(sort_nums[i]===sort_nums[i+1]){}else{final_length.push(arr_length)arr_length=1}i++}final_length.sort((a, b) => a - b )let result = final_lengthreturn result[result.length-1]
};

在这里插入图片描述

能通过,但时间复杂度是O(nlogn),谈谈思路并优化代码结构:

  • 从小到大排序数组nums
  • 遍历数组,遇到连续增大的项则arr_length加1,遇到相同的项则不做处理
  • 遇到不连续的项则将arr_length的值记录在新数组中,并将arr_length重置为1。
  • 新思路是每次循环都更新最大的arr_length值,和我的思路不太一样,我的思路是将数组每次不连续时的值都存在finally_arr数组中,最后再进行一个比较,取出最大的arr_length。

优化代码后

var longestConsecutive = (nums) => {if (nums.length === 0) return 0nums.sort((a, b) => a - b)let max = 1let count = 1for (let i = 0; i < nums.length - 1; i++) {let cur = i, next = i + 1if (nums[cur] === nums[next]) continue // 相同就跳过本次循环if (nums[cur] + 1 === nums[next]) { // 发现连续项 count++count++} else { // 否则,count重置1count = 1}max = Math.max(max, count)}return max
}

思路2

方法2:Set 的查找是 O(1)

  • 查找 Set 中的元素的时间复杂度是 O(1),JS 的 Set 能给数组去掉重复元素
  • 将数组元素存入 set 中,遍历数组 nums
  • 如果 当前项 - 1 存在于 set ,说明当前项不是连续序列的起点,跳过,继续遍历
  • 当前项没有“左邻居”,它就是连续序列的起点
  • 不断在 set 中查看 cur + 1 是否存在,存在,则 count +1
  • cur 不再有 “右邻居” 了,就算出了一段连续序列的长度

代码

var longestConsecutive = (nums) => {const set = new Set(nums) // set存放数组的全部数字let max = 0for (let i = 0; i < nums.length; i++) {if (!set.has(nums[i] - 1)) { // nums[i]没有左邻居,是序列的起点let cur = nums[i]let count = 1while (set.has(cur + 1)) { // cur有右邻居cur+1cur++ // 更新curcount++ }max = Math.max(max, count) // cur不再有右邻居,检查count是否最大}}return max
}作者:笨猪爆破组
链接:https://leetcode.cn/problems/longest-consecutive-sequence/solutions/277084/fang-fa-cong-yi-dao-nan-bing-cha-ji-fang-fa-bu-hui/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法3:哈希表

来源于力扣大佬

  • 哈希表的value存什么
  • key存数字,value存什么?
  • 新存入的数字,如果它找到相邻的数,它希望从邻居数那里获取什么信息?
  • 很显然它希望,左邻居告诉它左边能提供的连续长度,右邻居告诉它右边能提供的连续长度
  • 加上它自己的长度,就有了自己处在的连续序列的长度
    在这里插入图片描述

更新新序列的两端数字的value

同处一个连续序列的数字的value理应都相同,这是它们共同特征
但没有必要每个的value都是序列长度,只需要两端的数存序列的长度就好
因为靠的是两端和新数对接,序列是连续的,中间没有空位
序列的一端找到邻居后,将另一端对应的value更新为最新的序列长度

在这里插入图片描述

方法3 代码

var longestConsecutive = (nums) => {let map = new Map()let max = 0for (const num of nums) { // 遍历nums数组if (!map.has(num)) { // 重复的数字不考察,跳过let preLen = map.get(num - 1) || 0  // 获取左邻居所在序列的长度 let nextLen = map.get(num + 1) || 0 // 获取右邻居所在序列的长度 let curLen = preLen + 1 + nextLen   // 新序列的长度map.set(num, curLen) // 将自己存入 mapmax = Math.max(max, curLen) // 和 max 比较,试图刷新maxmap.set(num - preLen, curLen)  // 更新新序列的左端数字的valuemap.set(num + nextLen, curLen) // 更新新序列的右端数字的value}}return max
}作者:笨猪爆破组
链接:https://leetcode.cn/problems/longest-consecutive-sequence/solutions/277084/fang-fa-cong-yi-dao-nan-bing-cha-ji-fang-fa-bu-hui/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
http://www.lryc.cn/news/323767.html

相关文章:

  • css的text-shadow详解
  • Qt 利用共享内存实现一次只能启动一个程序(单实例运行)
  • 【生活知识-茶叶】
  • [AIGC] 在Spring Boot中指定请求体格式
  • 4核16G服务器租用优惠价格,26.52元1个月,半年149元
  • 2024 Mazing 3 中文版新功能介绍Windows and macOS
  • npm设置淘宝镜像
  • 现代卷积神经网络
  • 【wubuntu】披着Win11皮肤主题的Ubuntu系统
  • Kubernetes自动化配置部署
  • 2024年奥莱利科技趋势报告解析
  • 算法打卡Day14
  • Android Kotlin版封装EventBus
  • VUE父子组件的传参问题
  • 四、C#希尔排序算法
  • 华为认证网络工程师的市场需求大吗?
  • Pytorch:nn.Upsample() 和nn.ConvTranspose2d()
  • 百度交易中台之系统对账篇
  • Linux 服务升级:MySQL 主从(半同步复制) 平滑升级
  • python与excel第一节
  • 开发者必备神器 | 全能AI工具助你免费提升开发效率,每日轻松编写代码
  • 【RabbitMQ | 第七篇】RabbitMQ实现JSON、Map格式数据的发送与接收
  • ios symbolicatecrash 符号化crash
  • Rust 语言的 HashMap
  • 【目标检测基础篇】目标检测评价指标:mAP计算的超详细举例分析以及coco数据集标准详解(AP/AP50/APsmall.....))
  • 服务器与普通电脑的区别,普通电脑是否可以作为服务器使用
  • 长安链Docker Java智能合约引擎的架构、应用与规划
  • STM32 ESP8266模块的曲折探索
  • letcode::根据二叉树创建字符串
  • 6个免费的ChatGPT网站