题目描述
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
难度:Middle
前置知识
- hashmap
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这是一道最最长连续数字序列长度的题目, 官网给出的难度是hard
.
符合直觉的做法是先排序,然后用一个变量记录最大值,遍历去更新最大值即可,
代码:
if (nums.length === 0) return 0;
let count = 1;
let maxCount = 1;
// 这里其实可以不需要排序,这么做只不过是为了方便理解
nums = [...new Set(nums)].sort((a, b) => a - b);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] - nums[i] === 1) {
count++;
} else {
if (count > maxCount) {
maxCount = count;
}
count = 1;
}
}
return Math.max(count, maxCount);
但是需要排序时间复杂度会上升,题目要求时间复杂度为 O(n),
那么我们其实可以不用排序去解决的。
思路就是将之前”排序之后,通过比较前后元素是否相差 1 来判断是否连续“的思路改为
不排序而是直接遍历,然后在内部循环里面查找是否存在当前值的邻居元素
,但是马上有一个
问题,内部我们查找是否存在当前值的邻居元素
的过程如果使用数组,时间复杂度是 O(n),
那么总体的复杂度就是 O(n^2),完全不可以接受。怎么办呢?
我们换个思路,用空间来换时间。比如用类似于 hashmap 这样的数据结构优化查询部分,将时间复杂度降低到 O(1), 代码见后面代码部分
关键点解析
- 空间换时间
代码
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
set = new Set(nums);
let max = 0;
let temp = 0;
set.forEach(x => {
// 说明x是连续序列的开头元素
if (!set.has(x - 1)) {
temp = x + 1;
while (set.has(y)) {
temp = temp + 1;
}
max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字
}
});
return max;
};
复杂度分析
- 时间复杂度:$O(N)$
- 空间复杂度:$O(N)$
- 原题leetcode链接:https://leetcode-cn.com/problems/longest-consecutive-sequence/
更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com