Skip to main content

128. Longest Consecutive Sequence

分析

并查集 / 官方的规律方案

后者需要的思考更少

Pasted image 20220502192057.png

题解

超时 法一

function longestConsecutive(nums: number[]): number {
const map = {}
for (let i = 0; i < nums.length; i++) {
const n = nums[i]
map[n] = n + 1
}
let ans = 0
for (let i = 0; i < nums.length; i++) {
let cnt = 1
let currentN = nums[i]
let nextN = map[currentN]
while (map[nextN] !== undefined) {
cnt++
currentN = nextN
nextN = map[currentN]
}
ans = Math.max(ans, cnt)
}
return ans
};

也可以不用cnt

function longestConsecutive(nums: number[]): number {
const map = {}
for (let i = 0; i < nums.length; i++) {
const n = nums[i]
map[n] = n + 1
}
let ans = 0
for (let i = 0; i < nums.length; i++) {
let currentN = nums[i]
let nextN = map[currentN]
while (map[nextN] !== undefined) {
currentN = nextN
nextN = map[currentN]
}
ans = Math.max(ans, nextN - nums[i])
}
return ans
};

进行路径压缩

function longestConsecutive(nums: number[]): number {
const map = {}
for (let i = 0; i < nums.length; i++) {
const n = nums[i]
map[n] = n + 1
}
let ans = 0
for (let i = 0; i < nums.length; i++) {
let currentN = nums[i]
let nextN = map[currentN]
while (map[nextN] !== undefined) {
currentN = nextN
nextN = map[currentN]
}
map[nums[i]] = nextN
}
Object.keys(map).forEach(key => {
const a = Number(key)
const b = map[key] === undefined ? a : map[key] - 1
ans = Math.max(ans, b - a + 1)
})
return ans
};

官方题解

function longestConsecutive(nums: number[]): number {
const memo = new Set(nums)
let ans = 0

for (const num of memo) {
if (memo.has(num - 1)) {
continue
}
let consecutiveSequenceNum = num
while (memo.has(consecutiveSequenceNum + 1)) {
consecutiveSequenceNum += 1
}
// 跳出的时候证明 consecutiveSequenceNum + 1 不存在于 memo 因此 consecutiveSequenceNum 为边界值
ans = Math.max(ans, consecutiveSequenceNum - num + 1)
}
return ans
};