HashMap plus union found solution using Java programming!


  • 5
    T
    class Solution {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            if(accounts==null || accounts.size()<1){
                return new ArrayList<>();
            }
            int[] parent = new int[accounts.size()];
            for(int i=0;i<parent.length;i++){
                parent[i] = i;
            }
            
            Map<String,Integer> map = new HashMap<>();
            for(int i=0;i<accounts.size();i++){
                List<String> eleStrs = accounts.get(i);
                for(int j=1;j<eleStrs.size();j++){
                    String email = eleStrs.get(j);
                    if(map.containsKey(email)){
                        int pre_id = map.get(email);
                        int cur_id = i;
                        int parent_pre_id = findParent(parent,pre_id);
                        int parent_cur_id = findParent(parent,cur_id);
                        if(parent_pre_id!=parent_cur_id){
                            parent[parent_cur_id] = parent_pre_id;
                        }
                    }else{
                        map.put(email,i);
                    }
                }
            }
            
            Map<Integer,Set<String>> hm = new HashMap<>();
            for(int i=0;i<parent.length;i++){
                int index = findParent(parent,i);
                if(!hm.containsKey(index)){
                    hm.put(index,new HashSet<>());
                }
                
                Set<String> temp = new HashSet<>();
                for(int j=1;j<accounts.get(i).size();j++){
                    temp.add(accounts.get(i).get(j));
                }
                hm.get(index).addAll(temp);
            }
            
            List<List<String>> ans = new ArrayList<>();
            for(Integer id : hm.keySet()){
                ans.add(new ArrayList<>());
                ans.get(ans.size()-1).add(accounts.get(id).get(0));
                
                List<String> addemails = new ArrayList<>(hm.get(id));
                Collections.sort(addemails);
                ans.get(ans.size()-1).addAll(addemails);
            }
            
            return ans;
            
        }
        
        public int findParent(int[] parent,int index){
                 while(index!=parent[index]){
                     parent[index] = parent[parent[index]];
                     index = parent[index];
                 }
            
                 return index;
        }
    }
    

  • 1
    P

    @tiandiao123
    Nice solution! Here's another implementation with very similar idea of just using one hashMap and lists instead of using multiple HashMap and HashSet.

     private int findParent(int i, int[] parents)
        {
             while(parents[i]!= -1)
                 i=parents[i];
             return i;
        }
        
         public List<List<String>> accountsMerge(List<List<String>> accounts) {
             //union find
             int len =accounts.size();
             int[]  parents = new int[len];
             ArrayList<LinkedList<String>> res = new ArrayList<>();
             List<List<String>> ans= new LinkedList<>();
             Arrays.fill(parents, -1);
             int i=0;
             HashMap<String, Integer> map = new HashMap<>();
             //initlize res
             for(int m=0; m<len; m++)
             {
                 res.add(new LinkedList<>());
             }
            for(List<String> account: accounts)
            {
                int j =0;
                int op =i, np =i;
                for(String email: account)
                {
                    if(j++==0)
                        continue;
                    if(!map.containsKey(email))
                    {
                        map.put(email, i);
                        res.get(op).add(email);
                    }
                    else
                    {
                        int old = map.get(email);
                        LinkedList<String> tmp=res.get(op);
                        np= findParent(op,parents);
                        op=findParent(old,parents);
                        if(op!=np)    
                        {//set new i's parent as old
                          parents[np]=op;     //!! weightest merge
                          res.get(op).addAll(tmp);
                          res.set(tmpIdx,new LinkedList<String>());
                        }
                    }
                   
                }
                i++;
            }
             
             for(int m=0; m<len; m++)
             {
                 LinkedList list =res.get(m);
                 if(list.isEmpty())
                     continue;
                 Collections.sort(list);
                 list.addFirst(accounts.get(m).get(0));
                 ans.add(list);
             }
             return ans;
             
         }
    

Log in to reply
 

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