1
class Solution {
2
public:
3
    int longestConsecutive(vector<int>& nums) {
4
      unordered_set<int> set(nums.begin(), nums.end()); // 快速将vector容器转化为set哈希表
5
      int res = 0; //题目中数组可以为空所以要考虑此情况
6
      for(auto num : set){
7
        if(set.count(num - 1)){ // 如果该值不是有序序列最小值 则跳过
8
          continue;
9
        }
10
        int y = num;
11
        while(set.count(y)){
12
          y++;
13
        }
14
        res = max(res, y - num); //此时y为序列末尾后一位 直接减去num就是长度 这么设置变量优化很多冗余操作
15
      }
16
      return res;
17
    }
18
};

1
class Solution {
2
private:
3
    unordered_map<int, int> parent;
4
    unordered_map<int, int> size;
5
    int maxSize = 0; // 记录全场最大的集合大小
6

7
    //查：路径压缩
8
    int find(int x){
9
      if(parent[x] == x){ // 如果找到一个父节点为自己的点 说明是该分类的root节点
10
        return x;
11
      }
12
      parent[x] = find(parent[x]); // 在递归寻找的同时将自己的父节点设为root节点 以压缩并查集
13
      return parent[x];
14
    }
15
    /*
16
        由于以上递归写法可能引起栈溢出，以下有更推荐的迭代写法：
17
        int find(int x){
18
            int root = x;
19
            while(parent[root] != root){
20
                root = parent[root];
21
            }
22

23
            手动回溯进行路径压缩
24
            int curr = x;
25
            while(curr != root){
26
                int next = parent[curr];
27
                parent[next] = root;
28
                curr = next;
29
            }
30

31
            return root;
32
        }
33
    */
34

35
    //并：按大小合并（小的并入大的）
36
    void unite(int x, int y){
37
      int rootX = find(x);
38
      int rootY = find(y);
39

40
      if(rootX == rootY) return;
41

42
      //让小的集合归入大的集合下 若1 合并到 2，然后2 再和 3进行合并，这时候应该是2 作为 3的根节点，因为2的size更大
43
      if(size[rootX] < size[rootY]){
44
        parent[rootX] = rootY;
45
        size[rootY] += size[rootX];
46
        maxSize = max(maxSize, size[rootY]);
47
      }else{
48
        parent[rootY] = rootX;
49
        size[rootX] += size[rootY];
50
        maxSize = max(maxSize, size[rootX]);
51
      }
52
    }
53
public:
54
    int longestConsecutive(vector<int>& nums) {
55
      if(nums.empty()) return 0;
56
      //初始化并查集 - 自立门户
57
      for(int x : nums){
58
        if(!parent.count(x)){ // 去重
59
          parent[x] = x;
60
          size[x] = 1;
61
          maxSize = max(maxSize, 1);
62
        }
63
      }
64

65
      //寻找相邻元素进行合并
66
      for(int x : nums){
67
        if(parent.count(x + 1)){
68
          unite(x, x + 1);
69
        }
70
      }
71

72
      return maxSize;
73
    }
74
};