Java实现 LeetCode 721 账户合并（并查集）

小灰灰 2023-07-24 05:40 27阅读 0赞

## 721. 账户合并 ##

给定一个列表 accounts，每个元素 accounts\[i\] 是一个字符串列表，其中第一个元素 accounts\[i\]\[0\] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。

现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。

合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。

例子 1:

Input: 
    accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
    Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
    Explanation: 
      第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。 
      第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
      我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
      ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。

注意：

accounts的长度将在\[1，1000\]的范围内。  
accounts\[i\]的长度将在\[1，10\]的范围内。  
accounts\[i\]\[j\]的长度将在\[1，30\]的范围内。

PS：  
并查集，先找到每一个邮件的父级，就是最顶层的那个并查集，  
然后在手动循环一遍，找到所有的父级  
然后在把他父级的名称拿过来（找最原来的list的第一个字符串，就是他的名字）  
这里

## `lll.add(accounts.get(e.getValue()).get(0));` ##

e.getValue就是我当时放入的f\[i\]，就是最顶层的下标，然后再找名字  
后面就…………就可以了，（小编表达能力比较差，有不清楚的欢迎评论）

class Solution { 
      public static int [] f  = new int[1010];
        public static void changeFather(int a,int b){ 
            int a_ = find(a);
            int b_ = find(b);
            if(a_==b_)
                return;
                //赋值的时候也是把旧的赋值给新的
            f[b_]= a_;
    
        }
        public static int find(int x){ 
            while(x!=f[x]){ 
                x = f[x];
            }
            return x;
        }
        public List<List<String>> accountsMerge(List<List<String>> accounts) { 
            int len = accounts.size();
            for (int i = 0; i < 1010; i++) { 
                f[i]=i;
            }
            HashMap<String ,Integer> m = new HashMap<>();
            for (int i = 0; i <len; i++) { 
                List<String> list = accounts.get(i);
                for (int j = 1; j < accounts.get(i).size(); j++) { 
                    if(m.containsKey(list.get(j))){ 
                         //查找(左面是旧的右面是新的)
                        changeFather(m.get(list.get(j)),i);
                    }
                    else{ 
                        //没有就给他当前的
                        m.put(list.get(j),f[i]);
                    }
                }
            }
            //在循环一遍，找到所有的父级
            //key是邮箱，value是他的父级
            for(Map.Entry<String ,Integer> s:m.entrySet()){ 
                s.setValue(find(s.getValue()));
            }
            Map<Integer,List<String>> mm = new HashMap<>();
            for (Map.Entry<String,Integer> e:m.entrySet()) { 
                if(!mm.containsKey(e.getValue())){ 
                    List<String> lll = new ArrayList<>();
                    //把他父级的对应的名称拿过来
                    lll.add(accounts.get(e.getValue()).get(0));
                    mm.put(e.getValue(),lll);
                }
                //如果有名字了，直接添加
                mm.get(e.getValue()).add(e.getKey());
            }
            //把最后的结果加起来
            List<List<String>> ans = new LinkedList<>();
            for (Map.Entry<Integer,List<String>> e:mm.entrySet()) { 
                List<String> lt = e.getValue();
                Collections.sort(lt);
                ans.add(lt);
            }
            return ans;
        }
    }