题目描述

给定一个未排序的整数数nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度O(n)的算法解决此问题。

解法一：并查集

这道题目可以用并查集来解决。初始状态下数组中的每个元素都是一个独立的集合，然后遍历数组，将当前元素相邻的 元素合并到一个集合，最后返回所有集合中元素个数最多的数量。这里要注意去重。

#include <vector>
#include <unordered_map>

class UnionFind {
public:
    UnionFind(int num) {
        for (int i = 0; i < num; ++i) {
            parent_.push_back(i);
            size_.push_back(1);
        }
    }

    void unite(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parent_[pRoot] = qRoot;
        size_[qRoot] += size_[pRoot];
    }

    int find(int p) {
        if (p != parent_[p]) {
            parent_[p] = find(parent_[p]);
        }
        return parent_[p];
    }

    int maxConnectedSize() {
        int ret = 0;
        for (int i = 0; i < parent_.size(); ++i) {
            if (parent_[i] == i) {
                ret = std::max(ret, size_[i]);
            }
        }
        return ret;
    }

private:
    std::vector<int> parent_;
    std::vector<int> size_;
};

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) {

        // 用于记录元素和下标的对应关系，同时也用来去重
        std::unordered_map map;

        // 构造一个并查集实例，以下标来表示nums中的一个数字
        // 初始状态下，每个元素都是独立的集合
        UnionFind uf(nums.size());

        for (int i = 0; i < nums.size(); ++i) {
            // 去重
            if (map.find(nums[i]) != map.end()) {
                continue;
            }

            // 将比当前元素小1的元素连接起来
            if (map.find(nums[i] - 1) != map.end()) {
                uf.unite(i, map[nums[i] - 1]);
            }

            // 将比当前元素大1的元素连接起来
            if (map.find(nums[i] + 1) != map.end()) {
                uf.unite(i, map[nums[i] + 1]);
            }

            // 记录元素和下标的对应关系
            map[nums[i]] = i;
        }

        // 返回最终所有集合中，元素最多的集合的元素个数
        return uf.maxConnectedSize();
    }
};