LeetCode: 128. 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.

题目大意： 给定未排序的整数数组，找到其连续被元素的最长序列。

解题思路 —— 并查集

利用并查集，将相邻元素合并为一个集合，求得最大集合的元素个数即可。
如下图描述了题目例子中的元素形成的集合，由图可知，最大集合为 {1,2,3,4}, 其大小为 4.

AC 代码

class Solution 
{
    // 求出 curNum 和 curNum+1 的 consecutiveNum （O(1)）
    void Union(vector<int>& consecutiveNum, int curNum, unordered_map<int, int>& num2Idx)
    {
        int curNumIdx = num2Idx[curNum];

        if(num2Idx.find(curNum-1) != num2Idx.end() && consecutiveNum[num2Idx[curNum-1]] != -1)
        {
            consecutiveNum[curNumIdx] = num2Idx[curNum - 1];
        }
        else 
        {
            consecutiveNum[curNumIdx] = curNumIdx;
        }

        if(num2Idx.find(curNum+1) != num2Idx.end() && consecutiveNum[num2Idx[curNum+1]] != -1)
        {
            consecutiveNum[num2Idx[curNum+1]] = consecutiveNum[curNumIdx];
        }
    }

    // 收缩关系集(O(n))
    int findMinConsecutiveNum(vector<int>& consecutiveNum, int curNumIdx)
    {
        if(consecutiveNum[curNumIdx] == curNumIdx || consecutiveNum[curNumIdx] == -1) return curNumIdx;
        consecutiveNum[curNumIdx] = findMinConsecutiveNum(consecutiveNum, consecutiveNum[curNumIdx]);

        return consecutiveNum[curNumIdx];
    }
public:
    int longestConsecutive(vector<int>& nums)
    {
        // consecutiveNum[i] 表示与 i 形成的最长连续序列的最小值的索引
        vector<int> consecutiveNum(nums.size(), -1);
        // 记录 num 到其 index 的映射(unordered_map 是散列表，存取复杂度为 O(1))
        // 重复元素只处理一个
        unordered_map<int, int> num2Idx;

        // 初始化 num2Idx... (O(n))
        for(size_t idx = 0; idx < nums.size(); ++idx)
        {
            num2Idx[nums[idx]] = idx;
        }

        // 计算 consecutiveNum （O(n)）
        for(int curNum : nums)
        {
            Union(consecutiveNum, curNum, num2Idx);
        }

        // 收缩关系 (O(n))
        for(size_t i = 0; i < consecutiveNum.size(); ++i)
        {
            findMinConsecutiveNum(consecutiveNum, i);
        }

        // 计算连续序列((O(n)))
        vector<int> counts(consecutiveNum.size(), 0);
        for(size_t i = 0; i < consecutiveNum.size(); ++i)
        {
            if(consecutiveNum[i] == -1) continue;
            ++counts[consecutiveNum[i]];
        }

        // 统计最大连续序列的长度((O(n)))
        int maxLong = 0;
        for(int x : counts)
        {
            maxLong = max(x, maxLong);
        }

        return maxLong;
    }
};