128. 最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public int longestConsecutive(int[] nums) {
        // 并查集
        int n = nums.length;
        int[] parent = new int[n];
        
        Map<Integer, Integer> map = new HashMap<>();
        // 初始化并查集
        for(int i = 0; i < n; i++){
            parent[i] = i;
            if(map.containsKey(nums[i])){
                continue;
            }
            map.put(nums[i], i);
        }

        for(int i = 0; i < n; i++){
            int num = nums[i];
            if(map.get(num) == i){
                // 只处理map中包含的index的角标进行去重
                if(map.containsKey(num-1)){
                    int idx = map.get(num-1);
                    uion(i, idx, parent);
                }

                if(map.containsKey(num+1)){
                    int idx = map.get(num+1);
                    uion(i, idx, parent);
                }
            }
        }


        // 遍历查找并查集中最多的集合
        int ans = 0;
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int i = 0; i < n; i++){
            int p = find(i, parent);
            int count = countMap.getOrDefault(p, 0) + 1;
            countMap.put(p, count);
            ans = Math.max(ans, count);
        }
        return ans;
    }

    public int find(int k, int[] parent){
        if(k != parent[k]){
            parent[k] = find(parent[k], parent);
        }
        return parent[k];
    }

    public void uion(int i, int j, int[] parent){
        int x = find(i, parent);
        int y = find(j, parent);
        if(x != y){
            parent[x] = y;
        }
    }
}