Longest Consecutive Sequence

Question

Problem Statement

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

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its
length: 4.

Clarification

Your algorithm should run in O(n) complexity.

题解

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

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return an integer
  5.      */
  6.     public int longestConsecutive(int[] num) {
  7.         if (num == null || num.length == 0) return 0;
  9.         // add number to hashset
  10.         Set<Integer> hashset = new HashSet<Integer>();
  11.         for (int n : num) {
  12.             hashset.add(n);
  13.         }
  15.         int lcs = 0;
  16.         for (int n : num) {
  17.             int i = n, count = 1;
  18.             hashset.remove(n);
  19.             // i--
  20.             while (hashset.contains(--i)) {
  21.                 count++;
  22.                 hashset.remove(i);
  23.             }
  24.             // i++
  25.             i = n;
  26.             while (hashset.contains(++i)) {
  27.                 count++;
  28.                 hashset.remove(i);
  29.             }
  30.             // update lcs
  31.             lcs = Math.max(lcs, count);
  32.         }
  34.         return lcs;
  35.     }
  36. }

源码分析

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

复杂度分析

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