一天一大 leet
题目（难度：困难）：
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
示例
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
抛砖引玉
- 要求算法的时间复杂度为 O(n),即限制了只能循环一次；
- 先对数组排序
- 循环数组记录后一个元素等于前一个元素+1或者等于前一个元素的数量
- 满足条件++，不然重置
- 与之前记录的值取最大值
- 个人觉得和题目的限制，虽然排序是用数组原生的方法做的，但是应该是多了一次排序的循环
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
if (nums.length < 2) return nums.length;
var _result = 1, middleValue = 1;
nums.sort((a, b) => a - b)
for (let index = 0; index < nums.length; index++) {
if (nums[index] === nums[index + 1]) {
continue // 跳出本次循环
} else if (nums[index] + 1 === nums[index + 1]) {
middleValue++
} else {
middleValue = 1
}
_result = Math.max(_result, middleValue);
}
return _result;
};官方答案
- 哈希表
我们考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配x+1,x+2,⋯ 是否存在，假设最长匹配到了 x+y，那么以 x 为起点的最长连续序列即为 x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不断枚举并更新答案即可。
对于匹配的过程，暴力的方法是O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至O(1) 的时间复杂度。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到)O(n2)（即外层需要枚举 O(n) 个数，内层需要暴力匹配 OO(n) 次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
var longestConsecutive = function(nums) {
let num_set = new Set();
for (const num of nums) {
num_set.add(num);
}
let longestStreak = 0;
for (const num of num_set) {
if (!num_set.has(num - 1)) {
let currentNum = num;
let currentStreak = 1;
while (num_set.has(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
};高手在民间
- Set 的查找
- Set 查找元素的时间复杂度是 O(1)，JS 的 Set 能给数组去掉重复元素
- 将数组元素存入 set 中，遍历数组 nums
- 如果 nums[i] - 1 存在于 set ，说明 nums[i] 不是连续序列的起点，跳过，继续遍历
- 当前项没有“左邻居”，它就是连续序列的起点
- 不断在 set 中查看 cur + 1 是否存在，存在，则 count +1
- cur 不再有 “右邻居” 了，就算出了一段连续序列的长度
var longestConsecutive = (nums) => {
const set = new Set(nums) // set存放数组的全部数字
let max = 0
for (let i = 0; i < nums.length; i++) {
if (!set.has(nums[i] - 1)) { // nums[i]没有左邻居，是序列的起点
let cur = nums[i]
let count = 1
while (set.has(cur + 1)) { // cur有右邻居cur+1
cur++ // 更新cur
count++
}
max = Math.max(max, count) // cur不再有右邻居，检查count是否最大
}
}
return max
}
- 哈希表
- 遍历原数组依次向map中存储原数组的值及其包含当前值的连续长度
- 当前值的连续长度有两部分组成：1、小于当前值的连续长度，2、大于当前值的连续长度
- 每次遍历结束同步map中的连续长度-供下次遍历中使用
- 更新返回值max
var longestConsecutive = (nums) => {
let map = new Map()
let max = 0
for (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) // 将自己存入 map
max = Math.max(max, curLen) // 和 max 比较，试图刷新max
map.set(num - preLen, curLen) // 更新新序列的左端数字的value
map.set(num + nextLen, curLen) // 更新新序列的右端数字的value
}
}
return max
}
菜鸡的自白
优化说明:
- 没有考虑到可以使用set去重所有循环中需要单独判断存在重复值的问题
- 哈希表天然解决了重复值的问题，但是每个数据均需要统计连续长度还需要实时更新，感觉理解起来会繁琐一点
- 个人觉得‘Set 的查找’和官方的方法是比较有意思的
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
if (nums.length < 2) return nums.length;
var _result = 1;
for (let index = 0; index < nums.length; index++) {
if (!nums.includes(nums[index] - 1)) {
let middleValue = nums[index];
let currentStreak = 1;
while (nums.includes(middleValue + 1)) {
middleValue += 1;
currentStreak += 1;
}
_result = Math.max(_result, currentStreak);
}
}
return _result;
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-06-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录