题目描述

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

解法一：并查集

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

 1#include <vector>
 2#include <unordered_map>
 3
 4class UnionFind {
 5public:
 6    UnionFind(int num) {
 7        for (int i = 0; i < num; ++i) {
 8            parent_.push_back(i);
 9            size_.push_back(1);
10        }
11    }
12
13    void unite(int p, int q) {
14        int pRoot = find(p);
15        int qRoot = find(q);
16        if (pRoot == qRoot) {
17            return;
18        }
19        parent_[pRoot] = qRoot;
20        size_[qRoot] += size_[pRoot];
21    }
22
23    int find(int p) {
24        if (p != parent_[p]) {
25            parent_[p] = find(parent_[p]);
26        }
27        return parent_[p];
28    }
29
30    int maxConnectedSize() {
31        int ret = 0;
32        for (int i = 0; i < parent_.size(); ++i) {
33            if (parent_[i] == i) {
34                ret = std::max(ret, size_[i]);
35            }
36        }
37        return ret;
38    }
39
40private:
41    std::vector<int> parent_;
42    std::vector<int> size_;
43};
44
45class Solution {
46public:
47    int longestConsecutive(std::vector<int>& nums) {
48
49        // 用于记录元素和下标的对应关系，同时也用来去重
50        std::unordered_map map;
51
52        // 构造一个并查集实例，以下标来表示nums中的一个数字
53        // 初始状态下，每个元素都是独立的集合
54        UnionFind uf(nums.size());
55
56        for (int i = 0; i < nums.size(); ++i) {
57            // 去重
58            if (map.find(nums[i]) != map.end()) {
59                continue;
60            }
61
62            // 将比当前元素小1的元素连接起来
63            if (map.find(nums[i] - 1) != map.end()) {
64                uf.unite(i, map[nums[i] - 1]);
65            }
66
67            // 将比当前元素大1的元素连接起来
68            if (map.find(nums[i] + 1) != map.end()) {
69                uf.unite(i, map[nums[i] + 1]);
70            }
71
72            // 记录元素和下标的对应关系
73            map[nums[i]] = i;
74        }
75
76        // 返回最终所有集合中，元素最多的集合的元素个数
77        return uf.maxConnectedSize();
78    }
79};