Longest Consecutive Sequence

Tags: Array, Union Find, Hard

Question

Problem Statement

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

Your algorithm should run in O(n) complexity.

Example:

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

题解

首先看题要求，时间复杂度为 O(n), 如果排序，基于比较的实现为 n \log n, 基数排序需要数据有特征。故排序无法达到复杂度要求。接下来可以联想空间换时间的做法，其中以哈希表为代表。这个题要求返回最长连续序列，不要求有序，非常符合哈希表的用法。由于给定一个数其连续的数要么比它小1，要么大1，那么我们只需往左往右搜索知道在数组中找不到数为止。结合哈希表查找为 O(1) 的特性即可满足要求。

Java

  1. class Solution {
  2.     public int longestConsecutive(int[] nums) {
  3.         if (nums == null || nums.length <= 0) return 0;
  4.         Set<Integer> sets = new HashSet<>(nums.length);
  5.         for (int num : nums) {
  6.             sets.add(num);
  7.         }
  9.         int result = 1;
  10.         for (int num : nums) {
  11.             int seq = 1;
  12.             int right = num, left = num;
  13.             // right
  14.             while (sets.contains(++right)) {
  15.                 seq++;
  16.                 sets.remove(right);
  17.             }
  18.             // left
  19.             while (sets.contains(--left)) {
  20.                 seq++;
  21.                 sets.remove(left);
  22.             }
  23.             sets.remove(num);
  24.             if (seq > result) result = seq;
  25.         }
  27.         return result;
  28.     }
  29. }

源码分析

首先使用 HashSet 建哈希表，然后遍历数组，依次往左往右搜相邻数，搜到了就从 Set 中删除。末尾更新最大值。

复杂度分析

时间复杂度和空间复杂度均为 O(n).