LeetCode 300. 最长连续序列(map + 朴素遍历)+(set + 优化遍历)—— JavaScript-爱代码爱编程
相似题:LeetCode 300. 最长上升子序列
本题链接:https://leetcode-cn.com/problems/longest-consecutive-sequence/
题描述:
解题思路(map + 遍历):
利用 map 表示当前元素是否存在数组中。
每次对当前元素进行向前和向后的遍历,统计该元素的连续序列的长度。
代码实现(map + 遍历):
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
let map = new Map();
let res = 0;
for (let i = 0; i < nums.length; i++) {
if (map.get(nums[i]) == undefined) {
let num = 1;
let index;
index = nums[i] - 1;
while(map.get(index) != undefined) {
index--;
num++;
}
index = nums[i] + 1;
while(map.get(index) != undefined) {
index++;
num++;
}
map.set(nums[i], 1);
res = res > num ? res : num;
}
}
return res;
};
时间复杂度:O(n^2)
空间复杂度:O(n)
优化思路(set + 遍历):
在上面的代码中,我们对数组中的每个元素都进行了向上和向下的搜寻,实际上,我们只要对一段连续序列中最小的元素开始向上搜寻即可。
即如果该元素在数组中没有前驱(x 的前驱是 x - 1),便开始从该元素向上搜寻。
利用 set 表示一个元素是否存在该数组中。
优化代码实现(set + 遍历):
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
let set = new Set(nums);
let res = 0;
for (let i = 0; i < nums.length; i++) {
if (set.has(nums[i] - 1) == false) {
let t = nums[i];
let num = 0;
while (set.has(t) == true) {
t++;
num++;
}
res = res > num ? res : num;
}
}
return res;
};
时间复杂度:O(n)
空间复杂度:O(n)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/ySFRaabbcc/article/details/111097714