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)