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

洛阳春-岑参

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

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

题目描述

思路分析

方法及其时间复杂度

法一暴力枚举：

法二哈希表遍历：

法三并查集：

个人总结

题目描述

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++; //数字相同时，下标加1
                else   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)