题目描述
标签：中等 数组
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
plaintext
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路
方法一：哈希表
这个思路比较简单，主要精力在优化上。初始想法是遍历数组，然后对于每个元素，去查看num+1，num+2…是否在数组中，这样的时间复杂度是O(n^3)（数组查找元素也有O(n)的复杂度）。
优化：
- 使用哈希表来存储数组中的元素，这样查找的时间复杂度就是O(1)了。
- 对于每个元素，只有当它的前一个元素不在数组中时，才去查找后面的元素，这样可以减少很多不必要的查找。也就是说，只有当num-1不在数组中时，才去查找num+1，num+2…是否在数组中。
javascript
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
const set = new Set(nums)
let max = 0
let cur = 0
for (let n of set) {
if (!set.has(n - 1)) {
let tmp = n
while (set.has(tmp)) {
cur++
tmp += 1
}
max = Math.max(max, cur)
cur = 0
}
}
return max
}
方法二：动态规划
这个方法是我最开始想到的能控制时间复杂度在O(n)的方法，但是我没有想到具体怎么实现，所以就没写出来。这个方法的思路是，使用一个map维护每个元素的最长连续序列长度，然后遍历数组，对于每个元素，查看num-1和num+1的最长连续序列长度，然后更新num-1和num+1的最长连续序列长度。这样的时间复杂度是O(n)。
javascript
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
const map = new Map()
let max = 0
for (let num of nums) {
if (!map.has(num)) {
let left = map.get(num - 1) || 0
let right = map.get(num + 1) || 0
let len = 1 + left + right
max = Math.max(max, len)
map.set(num, len)
map.set(num - left, len)
map.set(num + right, len)
}
}
return max
}
方法三：并查集
并查集这个概念涉及到知识盲区了，需要补补课。
javascript
/**
* @param {number[]} nums
* @return {number}
*/
class UnionFind {
constructor(nums) {
this.parent = new Map()
this.size = new Map()
for (let num of nums) {
this.parent.set(num, num)
this.size.set(num, 1)
}
}
find(x) {
if (this.parent.get(x) === x) return x
this.parent.set(x, this.find(this.parent.get(x)))
return this.parent.get(x)
}
union(x, y) {
let rootX = this.find(x)
let rootY = this.find(y)
if (rootX === rootY) return
this.parent.set(rootX, rootY)
this.size.set(rootY, this.size.get(rootX) + this.size.get(rootY))
}
getSize(x) {
return this.size.get(this.find(x))
}
}
var longestConsecutive = function (nums) {
const uf = new UnionFind(nums)
const map = new Map()
let max = 0
for (let num of nums) {
if (map.has(num)) continue
map.set(num, num)
if (map.has(num - 1)) uf.union(num, num - 1)
if (map.has(num + 1)) uf.union(num, num + 1)
max = Math.max(max, uf.getSize(num))
}
return max
}