问题描述

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 $O(n)$
$输入：[100,4,200,1,3,2]$
$输出：4$

解题报告

• 暴力查找
  最粗暴的想法，从每个数字出发，依次查找后面能达到的最长连续序列长度。加上一点优化：判断一个数 x 是否是某个连续序列的开头，首先判断 x-1 是否在数组中。
• 并查集
  将任意相差为1的两个数相连，当将数组遍历完，我们得到若干子树，节点数最大的那棵子树的节点数即为答案。

实现代码

• 暴力查找

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_map<int,int>mp;for(auto num:nums) mp[num]=1;int ans=0;for(int i=0;i<nums.size();i++){if(mp.count(nums[i]-1)) continue;int y=nums[i]+1;while(mp.count(y)){y++;}ans=max(ans,y-nums[i]);}return ans;}
};

• 并查集

class Solution{public:unordered_map<int,int>fa,cnt;int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}int merge(int x,int y){x=find(x);y=find(y);if(x==y) return cnt[x];fa[y]=x;cnt[x]+=cnt[y];return cnt[x];}int longestConsecutive(vector<int>&nums){if(nums.size()==0){return 0;}for(auto num:nums){fa[num]=num;cnt[num]=1;}int ans=1;for(auto num:nums){if(fa.count(num+1)){ans=max(ans,merge(num,num+1));}}return ans;}
};

参考资料

[1] Leetcode 128.最长连续序列
[2] 每日算法系列【LeetCode 128】最长连续序列