题目简介:
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 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;
} };
|