【力扣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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。