128.最长连续序列

链接：128.最长连续序列
难度：Medium
标签：并查集、数组、哈希表
简介：给定一个未排序的整数数组，找出最长连续序列的长度。

题解 1 - typescript

• 编辑时间：2020-06-06
• 执行用时：84ms
• 内存消耗：37.8MB
• 编程语言：typescript
• 解法介绍：排序去重遍历。

function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) return 0;
  nums = [...new Set(nums)].sort((a, b) => a - b);
  let max = 1;
  let nowMax = 1;
  let preNum = nums[0];
  for (const num of nums) {
    if (num === preNum + 1) {
      nowMax++;
    } else {
      max = nowMax > max ? nowMax : max;
      nowMax = 1;
    }
    preNum = num;
  }
  return max > nowMax ? max : nowMax;
}

题解 2 - typescript

• 编辑时间：2020-06-06
• 执行用时：76ms
• 内存消耗：37.2MB
• 编程语言：typescript
• 解法介绍：用哈希表进行 O(1)的查找，即最慢查找速度 O(n)。

function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) return 0;
  const set = new Set(nums);
  let max = 1;
  for (let num of set) {
    if (!set.has(num - 1)) {
      let nowMax = 1;
      while (set.has(++num)) nowMax++;
      max = nowMax > max ? nowMax : max;
    }
  }
  return max;
}

题解 3 - typescript

• 编辑时间：2021-04-30
• 执行用时：192ms
• 内存消耗：53.8MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function longestConsecutive(nums: number[]): number {
  nums = [...new Set(nums)];
  const len = nums.length;
  if (len === 0) return 0;
  const uf = new UnionFind(len);
  const map = new Map(nums.map((v, i) => [v, i]));
  const ansMap = new Map<number, number>();
  for (let i = 0; i < len; i++) {
    const num = nums[i];
    const num_minus = map.get(num - 1);
    if (num_minus) {
      uf.union(i, num_minus);
      const index = uf.find(i);
      ansMap.set(index, (ansMap.get(index) ?? 0) + 1);
    }
    const num_add = map.get(num + 1);
    if (num_add) {
      uf.union(i, num_add);
      const index = uf.find(i);
      ansMap.set(index, (ansMap.get(index) ?? 0) + 1);
    }
  }
  const cache: Record<number, number> = {};
  for (let i = 0; i < len; i++) {
    const num = uf.find(i);
    cache[num] = (cache[num] ?? 0) + 1;
  }
  return [...Object.entries(cache)].sort(([, c1], [, c2]) => c2 - c1)[0][1];
}