题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
设计并实现时间复杂度为 O(n) 的算法解决此问题。
样例
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是[1, 2, 3, 4]。它的长度为4。
题解
题目要求时间复杂度为$O(n)$，那么肯定不能排序，因为排序起码有$O(nlogn)$的复杂度。
下面我们通过两个角度来解决这道题：
1.哈希
我们先分析一个显然的暴力解法：先把所有数存到一个哈希集合中，然后双重循环遍历，判断其是否匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int longestConsecutive(vector<int>& nums) {
unordered_set<int> s;
for(int x:nums) s.insert(x);
int ans=0;
for(int x:s){
int l=1;
int n=x+1;
while(s.find(n)!=s.end()){
l++;
n++;
}
ans=max(ans,l);
}
return ans;
}
|
但是这样的时间复杂度太高，我们仔细分析可以发现原因是外层循环做了很多不必要的枚举。我们可以这样进行优化：每次都判断这个数x的前驱x-1存不存在，如果存在那么我们接下来枚举的肯定不是最长的序列，所以我们每次都需要枚举不存在前驱的数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s;
for(int x:nums) s.insert(x);
int ans=0;
for(int x:s){
if(s.find(x-1)==s.end()){
int l=1;
int n=x+1;
while(s.find(n)!=s.end()){
l++;
n++;
}
ans=max(ans,l);
}
}
return ans;
}
};
|
2.并查集
将连续的数字作为一个集合。那么扫描到一个数字，只要将它和它的下一个数字（假如存在）Union在一个集合即可。同时更新这个集合的元素个数。同时更新当前最长记录。
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
| class Solution {
public:
unordered_map<int, int> father;
unordered_map<int, int> cnt;
int findFather(int x) {
if (x == father[x]) return x;
return father[x] = findFather(father[x]);
}
void Union(int x, int y) {
int fx = findFather(x);
int fy = findFather(y);
if (fx != fy) {
father[fx]=fy;
cnt[fy]+=cnt[fx];
}
}
int longestConsecutive(vector<int>& nums) {
for(int x:nums){
father[x]=x;
cnt[x]=1;
}
int ans=0;
for(int x:nums){
if(father.find(x+1)!=father.end()){
Union(x,x+1);
ans=max(ans,cnt[findFather(x)]);
}
}
return ans;
}
};
|
这里用了一个cnt来记录集合元素数，因为如果最后再计算时间复杂度会超出。