题目描述：

给定一个没有重复值的整型数组arr，初始时认为arr中每一个数各自都是一个单独的集合，请设计一种叫UnionFind的结构，并提供以下两个操作。

（1）boolean isSameSet(int a,int b)：查询a和b这两个数是否属于一个集合。

（2）void union(int a,int b)：把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合。

要求：

如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单词调用isSameSet或union方法的平均时间复杂度为O(1)。

解答：

符合题目功能要求的结构就是并查集。

 

1 class Element
     
       { 2     public V value; 3     public Element(V value) { 4         this.value=value; 5     } 6 } 7 public class UnionFindSet
      
        { 8     public HashMap
       
        
         > elementMap; 9     public HashMap
         
          
           ,Element
           
            > fatherMap;10 public HashMap
            
             
              ,Integer> rankMap;11 12 public UnionFindSet(List
              
                list) {13 elementMap=new HashMap<>();14 fatherMap =new HashMap<>();15 rankMap=new HashMap<>();16 for (V value : list) {17 Element
               
                 element=new Element
                
                 (value);18 elementMap.put(value,element);19 fatherMap.put(element,element);20 rankMap.put(element,1);21 22 }23 }24 private Element
                 
                   findHead(Element
                  
                    element) {25 Stack
                   
                    
                     > path=new Stack<>();26 while(element!=fatherMap.get(element)) {27 path.push(element);28 element=fatherMap.get(element);29 }30 while (!path.isEmpty()) {31 fatherMap.put(path.pop(),element);32 }33 return element;34 }35 36 public boolean isSameSet(V a,V b) {37 if (elementMap.containsKey(a)&&elementMap.containsKey(b)) {38 return findHead(elementMap.get(a))==findHead(elementMap.get(b));39 }40 return false;41 }42 public void union(V a,V b) {43 if (elementMap.containsKey(a)&&elementMap.containsKey(b)) {44 Element
                     
                       aF=findHead(elementMap.get(a));45 Element
                      
                        bF=findHead(elementMap.get(b));46 if (aF!=bF) {47 Element
                       
                         big=rankMap.get(aF)>rankMap.get(bF)?aF:bF;48 Element
                        
                          small=big==aF?bF:aF;49 fatherMap.put(small,big);50 rankMap.put(big,rankMap.get(aF)+rankMap.get(bF));51 rankMap.remove(small);52 }53 }54 }55 }
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

欢迎评论，共同进步！！