题目简介：
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
1
2
3
| 输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
|
思路：
首先设置一个集合，用来去重，减少循环的次数。
为了减少循环的次数，当我们访问一个数时，若它的前驱也存在于集合中，比如{2,3,4,5,6}，3的前驱为2，因为已经有2的存在了，所以最长连续序列必不可能从3开始计数。
所以我们找那些集合中不存在前驱的数，并以该数为起始点，统计最长的连续序列，最后返回最大值即可。
由于循环时每个数最多被访问到1次，所以复杂度为O(n)。
代码如下：
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
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> statistics;
int maxNum = 0;
for(int i = 0; i < nums.size(); i++){
statistics.insert(nums[i]);
}
for(int num : statistics){
if(!statistics.count(num - 1)){
int sum = 1;
int temp = num + 1;
while(statistics.count(temp)){
sum++;
temp++;
}
maxNum = max(sum, maxNum);
}
}
return maxNum;
}
};
|
