union bind with HashSet


  • 0
    L

    M has some redundancies. so only need to loop the top right half.
    If already two sets has each, then combined;
    if one set has it, then add the other;
    if both not included in the sets, then add it.

    '''
    public int findCircleNum(int[][] M) {
    List<Set<Integer>> list=new ArrayList<>();
    int len=M.length;
    for(int i=0;i<len;i++)
    for(int j=i+1;j<len;j++)
    {
    if(M[i][j]==1){
    //combine i and j
    Set<Integer> list1=null;//new ArrayList<>();
    Set<Integer> list2=null;//new ArrayList<>();
    Set<Integer> list3=new HashSet<>();

                for(int k=0;k<list.size();k++){
                    Set<Integer> res=list.get(k);
                    if(res.contains(new Integer(i+1))){
                        list1=(res);
                        
                    }
                    if(res.contains(new Integer(j+1))){
                        list2=(res);
                    }
                }
                if(list1==null&&list2==null) {list3.add(i+1);list3.add(j+1);list.add(list3);}
                else if(list1==null) {list2.add(i+1);}
                else if(list2==null) {list1.add(j+1);}
                else {
                    list3=new HashSet<>(list1);
                    list3.addAll(list2);
                    list.remove(list1);
                    list.remove(list2);
                    list.add(list3);
                }
            }
        }
        int count=len;
        for(int i=0;i<list.size();i++) count-=(list.get(i).size()-1);
        return count;
    }
    

    '''


Log in to reply
 

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