Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/

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

For example, Given[100, 4, 200, 1, 3, 2],

Your algorithm should run in O(n) complexity.

Thoughts

这道题有两种解法. online是维持一个map, 记录num和包含它的最长sequence当前能有多长.

然后我们每遇到一个Num, 检查num-1和num+1是否在Map里, 如果在则意味着当前点能和他们构成更长的sequence, 我们就更新它所在的新生成的sequence的 boundary 的长度。 boundary怎么获得呢? 实际上当前节点既然能和其它点结合形成更长的sequence, 也就意味着num-/+1是sequence原来的boundary, 也就是说可以通过它们的len推出seq另一边是哪个数字。

offline解法也和boundary有关, 只是不再需要两边boundary, 要小的那边就够了。 我们先把所有数字都放到集合里. 然后遍历, 对num检查是否存在num - 1, 存在则意味着当前数字不是boundary, 不存在则分别检查num + 1, + 2, + 3...是否在set里. 依次检查每个boundary能最长有多长。由于每个元素只会遍历两次，本身的一次，以及从boundary往上遍历过来的一次，总时间O(N)。

Code

/*
 * @lc app=leetcode id=128 lang=cpp
 *
 * [128] Longest Consecutive Sequence
 *
 * https://leetcode.com/problems/longest-consecutive-sequence/description/
 *
 * algorithms
 * Hard (42.52%)
 * Likes:    2119
 * Dislikes: 106
 * Total Accepted:    226.6K
 * Total Submissions: 532.5K
 * Testcase Example:  '[100,4,200,1,3,2]'
 *
 * 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.
 * 
 * 
 */
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int len = 1;
            if (!s.count(nums[i] - 1)) {
                // 找到一个boundary。
                int num = nums[i] + 1;
                while (s.count(num)) {
                    ++len;
                    ++num;
                }
            }
            res = max(res, len);
        }
        return res;
    }
};

Analysis

时空复杂度都是O(N).