本文共 3094 字，大约阅读时间需要 10 分钟。

1070. 账户合并

描述

给定一个帐户列表，每个元素accounts [i]是一个字符串列表，其中第一个元素accounts [i] [0]是账户名称，其余元素是这个帐户的电子邮件。

• 账户个数在1~1000之间
• 每个账户下的电子邮件在1~10之间
• 每个字符串的长度在1~30之间

样例 1：

输入:	[		["John", "johnsmith@mail.com", "john00@mail.com"],		["John", "johnnybravo@mail.com"],		["John", "johnsmith@mail.com", "john_newyork@mail.com"],		["Mary", "mary@mail.com"]	]输出: 	[		["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],		["John", "johnnybravo@mail.com"],		["Mary", "mary@mail.com"]	]解释: 	第一个第三个John是同一个人的账户，因为这两个账户有相同的邮箱："johnsmith@mail.com".	剩下的两个账户分别是不同的人。因为他们没有和别的账户有相同的邮箱。	你可以以任意顺序返回结果。比如：		[		['Mary', 'mary@mail.com'],		['John', 'johnnybravo@mail.com'],		['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']	]	也是可以的。

题解

public class Solution {
       /**     * @param accounts: List[List[str]]     * @return: return a List[List[str]]     */    public List
   
    
     > accountsMerge(List
     
      
       > accounts) {
           // write your code here            List
       
        
         > result = new ArrayList<>(); if (accounts == null || accounts.size() == 0) { return result; } // 邮箱与用户的表 Map
         
           emailToOwner = mapEmailToOwner(accounts); // 将邮箱加入并查集 UnionFind uf = new UnionFind(); for (List
          
            account : accounts) { if (account.size() < 3) { continue; } Iterator
           
             i = account.iterator(); // 跳过用户名 i.next(); // 同一个用户的邮箱连起来 String cur = i.next(); while (i.hasNext()) { String next = i.next(); uf.connect(cur, next); cur = next; } } // 将每个相同的邮箱连起来 Map
            
             > rootEmailToEmails = new HashMap<>(); for (String email : emailToOwner.keySet()) { String root = uf.find(email); List
             
               emails = rootEmailToEmails.get(root); if (emails == null) { emails = new ArrayList<>(); rootEmailToEmails.put(root, emails); } emails.add(email); } // 将每个root email和用户名连起来 for (String rootEmail: rootEmailToEmails.keySet()) { List
              
                info = new ArrayList<>(); String owner = emailToOwner.get(rootEmail); info.add(owner); List
               
                 emails = rootEmailToEmails.get(rootEmail); Collections.sort(emails); info.addAll(emails); result.add(info); } return result; } private Map
                
                  mapEmailToOwner(List
                 
                  
                   > accounts) { Map
                   
                     emailToOwner = new HashMap<>(); for (List
                    
                      account : accounts) { Iterator
                     
                       i = account.iterator(); String owner = i.next(); while (i.hasNext()) { emailToOwner.put(i.next(), owner); } } return emailToOwner; } class UnionFind { private Map
                      
                        father; public UnionFind() { this.father = new HashMap<>(); } public String find(String x) { String p; String temp = x; do { p = temp; temp = father.get(temp); } while (temp != null); while (!x.equals(p)) { temp = father.get(x); father.put(x, p); x = temp; } return p; } public void connect(String a, String b) { String fatherA = find(a); String fatherB = find(b); if (!fatherA.equals(fatherB)) { father.put(fatherA, fatherB); } } }}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

最后说两句

非常感谢你阅读本文章，如果你觉得本文对你有所帮助，请留下你的足迹，点个赞，留个言，多谢~

作者水平有限，如果文章内容有不准确的地方，请指正。

希望小伙伴们都能每天进步一点点。

声明

本文由博客原创，转载请注明来源，谢谢~

转载地址：https://le-yi.blog.csdn.net/article/details/114265645 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！