C++ UNION_FIND almost O(n) 9ms, beats over 80%.


  • 0
    F
    class Solution {
    private:
        vector<int> id; 
        vector<int> size; // the depth for each element
        int ans; // the final ans
    public:
        int Find(int i){
            while(i != id[i]){
                id[i] = id[id[i]]; // path compression, make it close to O(1) :)
                i = id[i];
            }
            return i;
        }
        void Union(int i, int j){
            int rootx = Find(i);
            int rooty = Find(j);
            if(rootx != rooty){
                id[rooty] = rootx;
                size[rootx] += size[rooty]; // update the depth
                ans = max(ans, size[rootx]); 
            }
        }
        int longestConsecutive(vector<int>& nums) {
            if(nums.size() == 0){
                return 0;
            }
            unordered_map<int,int> m; // val -> index
            ans = 1;  // at least 1 if not empty
            id = vector<int>(nums.size(), 0);
            for(int i = 0; i< nums.size();i++){
                id[i] = i;
            }
            size = vector<int>(nums.size(), 1);
            for(int i = 0; i< nums.size(); i++){
                if(m.find(nums[i]) == m.end()){
                    m[nums[i]] = i;
                    if(m.find(nums[i]-1) != m.end()){
                        Union(i, m[nums[i]-1]);
                    }
                    if(m.find(nums[i]+1) != m.end()){
                        Union(i, m[nums[i]+1]);
                    }
                }
            }
            return ans;   
        }
    };
    

Log in to reply
 

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