share my union find solution O(n) + O(n). Easily understood for begine


  • 0
    A
    class UnionFind
    {
    private:
        unordered_map<int, int> father;
        unordered_map<int, int> ssize;
        
    public:
        int find(int x)
        {
            int parent = x;
            while(parent != father[parent]) parent = father[parent];
            int bigdaddy = parent;
            
            while(x != father[x])
            {
                int tmp = father[x];
                father[x] = bigdaddy;
                x = tmp;
            }
            return bigdaddy;
        }
        
        void union_(int a, int b)
        {
            int fa = find(a);
            int fb = find(b);
            if (fa != fb)
            {
                father[fa] = fb;
                ssize[fa] = ssize[fb] = ssize[fa] + ssize[fb];
            }
        }
        
        UnionFind(vector<int> &nums)
        {
            for (int i = 0; i < nums.size(); i++)
            {
                father[nums[i]] = nums[i];
                ssize[nums[i]] = 1;
            }
        }
        
        int getmaxsize()
        {
            int result = 0;
            for (auto it : ssize) result = max(result, it.second);
            return result;
        }
    
    };
    
    class Solution
    {
    public:
        int longestConsecutive(vector<int>& nums)
        {
            UnionFind uf = UnionFind(nums);
            unordered_set<int> s;
            for (int i = 0; i < nums.size(); i++) s.insert(nums[i]);
            
            for (int i = 0; i < nums.size(); i++)
            {
                if (s.count(nums[i] - 1)) uf.union_(nums[i], nums[i] - 1);
                if (s.count(nums[i] + 1)) uf.union_(nums[i] + 1, nums[i]);
            }
            return uf.getmaxsize();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.