05 August 2008
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
没有排序的数组里面寻找最长的子序列，要求时间复杂度是O(n)。
1) 排序后，检查当前元素是否比上一个元素大1，找到最大连续的长度，O(nlogn)，不行；
2) 没有空间复杂度的要求，于是可以额外用一个HashSet，把数组里面所有的元素放入到set里面，然后遍历数组，对每个元素都进行移除操作，同时用两个指针prev和next求出当前元素的构成连续数列的前面和后面一个数，继续检查prev和next是否在set中存在，如果存在就继续移除，最后用next - prev - 1（因为两个指针指向的元素在set中不存在的时候才停止移除，所以有-1），对每个元素都进行这样的操作后求出连续序列最大的。
3) 也可以采用HashMap来做，刚开始map为空，然后遍历所有数组中的元素，如果该数字不在map中，那么分别检查前后两个数字是否在map中，如果在，则返回其哈希表中映射值，若不在，则返回0，将prev+next+1作为当前数字的映射，并更新result结果，然后更新num-left和num-right的映射值。
这其实是动态规划的思想，时间复杂度O(n)。
4) Union Find
HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
HashSet<Integer> set = new HashSet<>();
int result = 0;
//将数组里的所有元素放到HashSet里面
for (int num : nums) set.add(num);
for (int num : nums) {
if (set.remove(num)) {//Java的remove方法是有返回值的，同样add也有
int prev = num - 1, next = num + 1;
while (set.remove(prev)) prev--;
while (set.remove(next)) next++;
result = Math.max(result, next - prev - 1);
}
}
return result;
}
}
HashMap动态规划
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
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
HashMap<Integer, Integer> map = new HashMap<>();
int result = 0;
for (int num : nums) {
if (!map.containsKey(num)) {
//注意这里的prev和next是元素在HashMap中的索引值
int prev = map.containsKey(num - 1) ? map.get(num - 1) : 0;
int next = map.containsKey(num + 1) ? map.get(num + 1) : 0;
int sum = prev + next + 1;
map.put(num, sum);
result = Math.max(result, sum);
map.put(num - prev, sum);
map.put(num + next, sum);
}
}
return result;
}
}
备忘录法，dfs形成的递归树中有重复子结构。 比如[100, 4, 200, 1, 3, 2] ，遍历4时，已经将dfs(3),dfs(2),dfs(1)的情况给遍历过了，因此，再往后递归的时候，我们应该剪枝。 于是添加备忘录Map。
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
class Solution {
Set<Integer> checkInNums = new HashSet<>(); //初始化Set用来判断数字是否在nums中
Map<Integer, Integer> m = new HashMap<>(); //备忘录
public int longestConsecutive(int[] nums) {
if(nums.length == 0)
return 0;
for(int i = 0; i < nums.length; i++)
checkInNums.add(nums[i]);
int res = 0;
for(int i = 0; i < nums.length; i++)
res = Math.max(res, dfs(nums[i]));
return res;
}
//返回小于等于当前数的最大连续序列的长度
public int dfs(int cur) {
if(m.containsKey(cur))
return m.get(cur);
int len = 1; //当前长度为1
if(checkInNums.contains(cur-1))
len += dfs(cur-1);
m.put(cur, len);
return len;
}
}
Union Find模板
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) {
if (nums == null || nums.length == 0) {
return 0;
}
HashMap<Integer, Integer> map = new HashMap<>(); //k-v: 元素 - 元素位置
int[] parent = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
parent[i] = i;
if (map.containsKey(nums[i])) {// 先把所有元素设为自己的leader，顺便除重
continue;
}
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
// 遇到相邻的元素，并且leader不一样，做union操作
if (map.containsKey(nums[i] - 1) && find(i, parent) != find(map.get(nums[i] - 1), parent)) {
union(i, map.get(nums[i] - 1), parent);
}
if (map.containsKey(nums[i] + 1) && find(i, parent) != find(map.get(nums[i] + 1), parent)) {
union(i, map.get(nums[i] + 1), parent);
}
}
// 找到parent中value最多的元素，代表某老大出现的次数最多，因此该集团的成员最多
int maxLen = 0;
int[] count = new int[parent.length];
for (int val : map.values()) {
int currParent = find(val, parent);
count[currParent]++;
maxLen = Math.max(maxLen, count[currParent]);
}
return maxLen;
}
// 以下为Union Find代码，
private int find(int p, int[] parent) {
if (p == parent[p]) {
return parent[p];
}
parent[p] = find(parent[p], parent); // 路径压缩，到最终leader
/**路径压缩的迭代写法
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
*/
return parent[p];
}
private void union(int p, int q, int[] parent) {
int f1 = find(p, parent);
int f2 = find(q, parent);
if (f1 != f2) {
parent[f1] = f2;
}
}
}
Union Find 做成class
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
63
64
65
66
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// 首次遍历，与邻居结盟
UnionFind uf = new UnionFind(nums);
for (int v : nums)
uf.union(v, v + 1); // uf.union() 结盟
// 二次遍历，记录领队距离
int max = 1;
for (int v : nums) {
max = Math.max(max, uf.find(v) - v + 1); // uf.find() 查找领队
}
return max;
}
// Union Find类代码
class UnionFind {
private int count;
private Map<Integer, Integer> parent; // (curr, leader)
UnionFind(int[] arr) {
count = arr.length;
parent = new HashMap<>();
for (int v : arr)
parent.put(v, v); // 初始时，各自为战，自己是自己的领队
}
// 结盟
void union(int p, int q) {
// 不只是 p 与 q 结盟，而是整个 p 所在队伍 与 q 所在队伍结盟
// 结盟需各领队出面，而不是小弟出面
Integer rootP = find(p), rootQ = find(q);
if (rootP == rootQ) return;
if (rootP == null || rootQ == null) return;
// 结盟
parent.put(rootP, rootQ); // 谁大听谁
// 应取 max，而本题已明确 p < q 才可这么写
// 当前写法有损封装性，算法题可不纠结
count--;
}
// 查找领队
Integer find(int p) {
if (!parent.containsKey(p))
return null;
// 递归向上找领队
int root = p;
while (root != parent.get(root))
root = parent.get(root);
// 路径压缩：扁平化管理，避免日后找领队层级过深
while (p != parent.get(p)) {
int curr = p;
p = parent.get(p);
parent.put(curr, root);
}
return root;
}
}
}