128 Longest Consecutive Sequence

Search…

128. Longest Consecutive Sequence​
1. Question
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.
Your algorithm should run in O(n) complexity.
2. Implementation
(1) Hash Table + Union Find 
1
class Solution {
2
    public int longestConsecutive(int[] nums) {
3
        Map<Integer, Integer> map = new HashMap<>();
4
        int n = nums.length;
5
​
6
        UnionFind uf = new UnionFind(n);
7
​
8
        for (int i = 0; i < nums.length; i++) {
9
            if (map.containsKey(nums[i])) {
10
                continue;
11
            }
12
​
13
            map.put(nums[i], i);
14
​
15
            if (map.containsKey(nums[i] - 1)) {
16
                uf.union(i, map.get(nums[i] - 1));
17
            }
18
​
19
            if (map.containsKey(nums[i] + 1)) {
20
                uf.union(i, map.get(nums[i] + 1));
21
            }
22
        }
23
        return uf.maxSize();
24
    }
25
​
26
    class UnionFind {
27
        int[] sets;
28
        int[] size;
29
        int count;
30
​
31
        public UnionFind(int n) {
32
            sets = new int[n];
33
            size = new int[n];
34
            count = n;
35
​
36
            for (int i = 0; i < n; i++) {
37
                sets[i] = i;
38
                size[i] = 1;
39
            }
40
        }
41
​
42
        public int find(int node) {
43
            while (node != sets[node]) {
44
                node = sets[node];
45
            }
46
            return node;
47
        }
48
​
49
        public void union(int i, int j) {
50
            int node1 = find(i);
51
            int node2 = find(j);
52
​
53
            if (node1 == node2) {
54
                return;
55
            }
56
​
57
            if (size[node1] < size[node2]) {
58
                sets[node1] = node2;
59
                size[node2] += size[node1];
60
            }
61
            else {
62
                sets[node2] = node1;
63
                size[node1] += size[node2];
64
            }
65
            --count;
66
        }
67
​
68
        public int maxSize() {
69
            int res = 0;
70
            for (int i = 0; i < size.length; i++) {
71
                res = Math.max(res, size[i]);
72
            }
73
            return res;
74
        }
75
    }
76
}
Copied!
3. Time & Space Complexity
时间复杂度O(n), 空间复杂度O(n)

Union Find

130 Surrounded Regions

Last modified 2yr ago

Copy link

Contents

128. Longest Consecutive Sequence

1. Question

2. Implementation

3. Time & Space Complexity

128. Longest Consecutive Sequence​

1. Question

2. Implementation

3. Time & Space Complexity

128. Longest Consecutive Sequence