union find weighted balancing path compression


  • 0
    public class Solution {
               HashMap<Integer,Integer> map;
               HashMap<Integer,Integer> size;
        public int longestConsecutive(int[] nums) {
            map = new HashMap<>();
            size =new HashMap<>();
           for(int num: nums)
           {
               if(map.containsKey(num)) continue;
               map.put(num,num);
               size.put(num,1);
               if(map.containsKey(num-1))
                   union(num,num-1);
               if(map.containsKey(num+1))
                   union(num,num+1);
           }
           int maxCount=0;
           for(int val : size.values()) maxCount=Math.max(val,maxCount);
           return maxCount;
        }
        
        public int root(int i)
        {
            while(map.get(i)!=i)
            {
                map.put(i,map.get(map.get(i)));
                i=map.get(i);
            }
            return i;
        }
        
        public void union( int i ,int j)
        {
            if(i==j) return;
            int root1=root(i);
            int root2=root(j);
            int size1=size.get(root1);
            int size2 =size.get(root2);
            if(size1<size2)
            {
                map.put(root1,root2);
                size.put(root2,size1+size2);
            }
            else{
                map.put(root2,root1);
                size.put(root1,size1+size2);
            }
        }
    }
    

Log in to reply
 

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