Longest Consecutive Sequence

Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Solution(javascript)

/*
 * @lc app=leetcode id=128 lang=javascript
 *
 * [128] Longest Consecutive Sequence
 */

// @lc code=start
class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((val, index) => index)
    this.size = new Array(n).fill(1)
    this.count = n
  }

  root(i) {
    while (this.parent[i] !== undefined && i !== this.parent[i]) {
      this.parent[i] = this.parent[this.parent[i]] // Path compression
      i = this.parent[i]
    }
    return i
  }

  connected(a, b) {
    return this.root(a) === this.root(b)
  }

  union(a, b) {
    const rootA = this.root(a)
    const rootB = this.root(b)
    if (rootA === rootB) {
      return
    }
    if (this.parent[rootA] < this.parent[rootB]) {
      this.parent[rootA] = rootB
      this.size[rootB] += this.size[rootA]
    } else {
      this.parent[rootB] = rootA
      this.size[rootA] += this.size[rootB]
    }
    this.count -= 1
  }

  getCount() {
    return this.count
  }
}

// /** Union Find similar to 952
//  * 需要去重
//  * @param {number[]} nums
//  * @return {number}
//  */
// const longestConsecutive = function (nums) {
//   const uf = new UnionFind(nums.length)
//   const map = {}
//   for (let i = 0; i < nums.length; i++) {
//     const num = nums[i]
//     if (map[num] === undefined) {
//       if (map[num + 1] !== undefined) {
//         uf.union(i, map[num + 1])
//       }
//       if (map[num - 1] !== undefined) {
//         uf.union(i, map[num - 1])
//       }
//       map[num] = i
//     }
//   }
//   return uf.size.reduce((acc, a) => Math.max(acc, a), 0)
// }

/** 脑力解法
 * 需要去重
 * @param {number[]} nums
 * @return {number}
 */
const longestConsecutive = function (nums) {
  const set = nums.reduce((acc, num) => acc.add(num), new Set())
  let max = 0
  for (const num of set) {
    if (!set.has(num - 1)) {
      let currentNum = num
      let count = 0
      while (set.has(currentNum)) {
        count += 1
        currentNum += 1
      }
      max = Math.max(count, max)
    }
  }
  return max
}
// @lc code=end

// console.log(
//   longestConsecutive([1, 2, 0, 1]),
// )