洛阳春-岑参
人到洛阳花似锦，偏我来时不逢春。
谁道三冬无春色，冰山高处万里银
目录
题目描述
思路分析
方法及其时间复杂度
法一 暴力枚举：
法二 哈希表遍历：
法三 并查集：
个人总结
题目描述
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)
个人总结
多日没刷题，又怀念刷题的感觉，今日重启每日一诗系列
