Longest Consecutive Sequence

描述

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

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

Your algorithm should run in O(n) complexity.

分析

如果允许O(nlogn)O(n \log n)的复杂度，那么可以先排序，可是本题要求O(n)。

由于序列里的元素是无序的，又要求O(n)，首先要想到用哈希表。

用一个哈希表存储所有出现过的元素，对每个元素，以该元素为中心，往左右扩张，直到不连续为止，记录下最长的长度。

代码

  1. // Longest Consecutive Sequence
  2. // Time Complexity: O(n)，Space Complexity: O(n)
  3. class Solution {
  4. public:
  5.     int longestConsecutive(const vector<int> &nums) {
  6.         unordered_set<int> my_set;
  7.         for (auto i : nums) my_set.insert(i);
  9.         int longest = 0;
  10.         for (auto i : nums) {
  11.             int length = 1;
  12.             for (int j = i - 1; my_set.find(j) != my_set.end(); --j) {
  13.                 my_set.erase(j);
  14.                 ++length;
  15.             }
  16.             for (int j = i + 1; my_set.find(j) != my_set.end(); ++j) {
  17.                 my_set.erase(j);
  18.                 ++length;
  19.             }
  20.             longest = max(longest, length);
  21.         }
  22.         return longest;
  23.     }
  24. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/linear-list/array/longest-consecutive-sequence.html