每日一题--最长连续序列

洛阳春-岑参

人到洛阳花似锦，偏我来时不逢春。

谁道三冬无春色，冰山高处万里银

题目描述

思路分析

方法及其时间复杂度

法一暴力枚举：

法二哈希表遍历：

法三并查集：

个人总结

题目描述

128. 最长连续序列 - 力扣（LeetCode）

思路分析

先预处理排序，再枚举所有连续区间并计算长度，选择最大的连续区间最长的那个。

方法及其时间复杂度

法一暴力枚举：

class Solution {
public:int longestConsecutive(vector<int>& nums) {sort(nums.begin(),nums.end());//先排序数组int n=nums.size();if(n==1) return 1; //为了防止下标越界，特殊处理int ans=0,Maxn=1; //记录最后答案，和记录连续区间的长度for(int i=1;i<n;++i){while(i<n&&(nums[i]==nums[i-1]+1||nums[i]==nums[i-1])){ //进入连续区间if(nums[i]==nums[i-1]) i++; //数字相同时，下标加1else   Maxn++,i++; //不相同说明连续，则计数器加1，下标加1}ans=max(Maxn,ans);  //每一个连续区间结束，选择最大的连续区间数作为答案Maxn=1;  //重置计数为1}return ans;}
};

时间复杂度O(nlogn) 排序的时间nlogn，遍历时间复杂度O(n)

法二哈希表遍历：

将数组全部插入哈希表，然后遍历哈希表，如果当前数-1在哈希表中不存在，就设当前数为连续区间的起点，一直在哈希表中查找当前的下一个，找到计数器加1，直到找不到为止，在更新最大值作为答案。

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> hash(nums.begin(),nums.end());  //将所有数插入哈希表int ans=0;for(const auto& x:hash){  //遍历哈希表if(!hash.count(x-1)){  //如果该数-1没有在哈希表，可以作为起点int y=x+1;  while(hash.count(y)) y++; //一直查找下一个数，直到找不到为止ans=max(ans,y-x);  //取每个区间的最大长度}}return ans;}
};

时间复杂度O(n)，空间复杂度O(n)

法三并查集：

假定原数组中的每个元素都以自己本身为根的集合，且每个集合大小都是1。

遍历数组元素，如果集合中存在当前元素-1或+1则合并到一个集合中。最后返回集合最大那个大小

class Solution {
public:unordered_map<int,int> pre; unordered_map<int,int> sz;int root(int x){while(pre[x]!=x) x=pre[x];  //循环找根节点return x;}void merge(int x,int y){  //启发式合并，合并两个集合x=root(x),y=root(y);if(x==y) return ;if(sz[x]>sz[y])swap(x,y);pre[x]=y;sz[y]+=sz[x];}int longestConsecutive(vector<int>& nums) {for(const auto& x:nums){if(!pre.count(x)) pre[x]=x,sz[x]=1;  //初始化并查集if(pre.count(x-1)) merge(x,x-1);    //如果存在x-1或x+1则合并if(pre.count(x+1)) merge(x,x+1);}int ans=0;for(const auto& t:sz){  //查找合并集合里最大的ans=max(ans,t.second);}return ans;}
};

时间复杂度O(nlogn) 空间复杂度O(n)