并查集应用-账户合并

前言

力扣连着出了好几天的并查集题目，应该是想让读者学不会并查集就别过年的意思...所以今天来记录一道并查集的应用，账户合并问题

题目

//给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其
//余元素是 emails 表示该账户的邮箱地址。 
//
// 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为
//人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。 
//
// 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：
//accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnn
//ybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Ma
//ry", "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"。 
//第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
//可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
//['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的

分析

先拆解一下题目

题设：有若干账户（数组），账户里包含了用户姓名（数组第一个元素）以及该用户的若干不重复的邮箱
目的：要将相同用户的账户进行合并（把相同用户的邮箱整合到一个数组中）

好题目分析完，先直观的对题目进行一些思考

1、将相同用户的账户合并，优先要找到相同用户。
2、因为存在重名情况，不可以根据用户名来区分（也就是不能直接用一个hashmap把用户名当key来存储）。
3、排除掉不能用用户名当key的情况，那么只能根据账户中拥有相同邮箱来标记同人。
4、最笨的办法，可以遍历每一个邮件，然后在全集中找这个邮箱的账户，把该账户合并，更新账户集，记录当前邮箱已经处理完毕，继续遍历其他邮箱。
5、显然，这种办法可行，但是时间复杂度太高了O(n2)，每个邮箱都要跟其他所有邮箱进行比较判断。要优化
6、在分析，我们的目的是通过相等的两个邮箱，把两个账户合并到一起。那么我们如果能够建立一个索引关系，通过一个账户的任意一个邮箱就可以快速找到账户，那么遇到相等的两个相等邮箱的时候，我们直接把一个集合纳入到另外一个集合就ok了。
7、可以把每一个账户看成一颗树，树里的每一个叶子节点都是邮箱，当另外一个账户拥有这课树的元素时，直接合并。那并查集的大概思路就出来了。

分析完毕，进行解题思路

1、首先需要遍历所有的邮箱，将每一个邮箱自身作为一个集合。
2、遍历所有账户，把账户中的邮箱合并到一棵树中。（注1）
3、把树的节点合并到一个数组。
4、把数组的第一个元素标记为名字，返回结果。

注1：
举个例子，现在有两个账户 accountA、accountB，accountA中包含emailA，emailB。accountB中包含emailA，emailC。遍历accountA的时候，我们将emailA、emailB合并到了一棵树中。在遍历accountB时，将emailA与emailC合并时，因为emailA已经所属于一颗构造好的树，所以实际上是将emailC纳入到这棵树来，完成了合并。

实现

并查集

class UnionFind {
    // 有多少个元素,初始化的时候就数组的长度就是多少,每一个元素初始的父节点都是自身,即根节点
    // 数组下标代表一个叶子节点,下标对应的值代表树的父节点.
    // 数组元素和下标相同的点,代表是根节点,找到根节点,就找到了元素所属的集合.
    int[] parent;

    // 初始化并查集,初始化时,每个元素都是根节点,每个元素都是一棵树
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 合并两棵树,将一棵树(下标)在数组中的值赋值为另外一棵树的下标值,即标记了所属同一颗树.
    public void union(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }

    // 找到下标和数组下标相同的点,这就是根节点.也就是找老大环节.
    public int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
}

实现逻辑

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        // 构建邮箱与并查集初始化时的索引关系
        Map<String, Integer> emailToIndex = new HashMap<String, Integer>();
        // 构建邮箱与用户的映射关系
        Map<String, String> emailToName = new HashMap<String, String>();
        int emailsCount = 0;
        // 遍历所有邮箱,找到一共有多少个邮箱即为有多少颗树
        for (List<String> account : accounts) {
            String name = account.get(0);
            int size = account.size();
            for (int i = 1; i < size; i++) {
                String email = account.get(i);
                if (!emailToIndex.containsKey(email)) {
                    // 每找到一颗不同的树,树的 总数+1
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email, name);
                }
            }
        }
        // 根据一共邮箱的数量(即树的数量,构建并查集)
        UnionFind uf = new UnionFind(emailsCount);
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            // 找到邮箱在并查集中对应的下标
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();
            for (int i = 2; i < size; i++) {
                // 逐一获取其他邮箱的下标
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                // 因为当前在一个account中,所以需要将两个邮箱合并,即合到一棵树中
                uf.union(firstIndex, nextIndex);
            }
        }
        // 构建森林中每颗树的根节点坐标与这棵树所有邮箱列表的映射关系
        Map<Integer, List<String>> indexToEmails = new HashMap<Integer, List<String>>();
        for (String email : emailToIndex.keySet()) {
            // 找到邮箱所在的树的根节点
            int index = uf.find(emailToIndex.get(email));
            // 构建邮箱集合,将邮箱添加到集合中
            List<String> account = indexToEmails.getOrDefault(index, new ArrayList<String>());
            account.add(email);
            indexToEmails.put(index, account);
        }
        // 构建结果
        List<List<String>> merged = new ArrayList<List<String>>();
        for (List<String> emails : indexToEmails.values()) {
            Collections.sort(emails);
            // 获取用户名
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<String>();
            // 第一位是用户名
            account.add(name);
            // 将邮箱补充进数据
            account.addAll(emails);
            merged.add(account);
        }
        return merged;
    }

}