128. Longest Consecutive Sequence

,

Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestConsecutive(int[] nums) {
        int maxLength = 0;

        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        for (int num : numSet) { // 注意此处遍历 numSet 比 nums 效率更高，因为没有重复元素
            if (!numSet.contains(num - 1)) {
                // 当前数字可能作为连续数字的起点
                int length = 0;
                while (numSet.contains(num)) {
                    length++;
                    num++;
                }
                maxLength = Math.max(maxLength, length);
            }
        }

        return maxLength;
    }
}

UnionFind

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
61
62
class Solution {
    private static class UnionFind {
        private final int[] parent;
        private final int[] size;

        public UnionFind(int count) {
            this.parent = new int[count];
            for (int i = 0; i < count; i++) {
                parent[i] = i;
            }
            this.size = new int[count];
            Arrays.fill(size, 1);
        }

        public int getRoot(int x) {
            if (x != parent[x]) {
                x = getRoot(parent[x]); // path compression
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x);
            int yRoot = getRoot(y);
            if (xRoot == yRoot) {
                return;
            }

            parent[xRoot] = yRoot;
            size[yRoot] += size[xRoot];
        }
    }

    public int longestConsecutive(int[] nums) {
        UnionFind unionFind = new UnionFind(nums.length); // 存储索引

        Map<Integer, Integer> valueToIndexMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (valueToIndexMap.containsKey(nums[i])) {
                continue; // 不处理重复数字
            }
            valueToIndexMap.put(nums[i], i);
            Integer index = valueToIndexMap.get(nums[i] - 1);
            if (index != null) {
                unionFind.union(i, index);
            }
            index = valueToIndexMap.get(nums[i] + 1);
            if (index != null) {
                unionFind.union(i, index);
            }
        }

        int maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == unionFind.getRoot(i)) {
                maxLength = Math.max(maxLength, unionFind.size[i]);
            }
        }

        return maxLength;
    }
}

References

128. Longest Consecutive Sequence
剑指 Offer II 119. 最长连续序列