leetcode-128: longest continuous sequence

题目

题目连接
给定一个未排序的整数数组 nums ,找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度.

请你设计并实现时间复杂度为 O(n) 的算法解决此问题.

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4].它的长度为 4.

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

解题

方法一：哈希表

class Solution {
    
public:
    int longestConsecutive(vector<int>& nums) {
    
        unordered_set<int> set;
        for(int num:nums) set.insert(num);//去重
        int res=0;
        for(int num:set){
    
            if(!set.count(num-1)){
    //To find the starting position of a contiguous sequence
                int cur_num=num;
                int cur_count=1;
                while(set.count(cur_num+1)){
    
                    cur_num++;
                    cur_count++;
                }
                res=max(res,cur_count);

            }
        }
        return res;
    }
};

方法二：并查集

class UnionFind{
    
private:
    vector<int> parent;
    vector<int> size;
public:
    UnionFind(int n){
    
        parent.resize(n);
        size.resize(n);
        for(int i=0;i<n;i++){
    
            parent[i]=i;
            size[i]=1;
        }
    }
    int find(int index){
    
        if(parent[index]==index) return index;
        return parent[index]=find(parent[index]);
    }
    void unite(int index1,int index2){
    
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
    
            parent[p1]=p2;
            size[p2]+=size[p1];
        }
    }
    int getMaxConn(){
    
        int res=0;
        for(int i=0;i<size.size();i++){
    
            res=max(res,size[i]);
        }
        return res;
    }

};

class Solution {
    
public:
    int longestConsecutive(vector<int>& nums) {
    
        int n=nums.size();
        UnionFind uf(n);
        unordered_map<int,int> mp;

        for(int i=0;i<n;i++){
    
            if(mp.count(nums[i])) continue;
            if(mp.count(nums[i]-1)){
    
                uf.unite(i,mp[nums[i]-1]);
            }
            if(mp.count(nums[i]+1)){
    
                uf.unite(i,mp[nums[i]+1]);
            }
            mp[nums[i]]=i;
        }
        return uf.getMaxConn();

    }
};