问题简介

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

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

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

示例

输入：
accounts = [["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"。 
第二个 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]的范围内。

分析

账户数据结构如图，邮箱和姓名都有可能重复，但是由于拥有相同邮箱的账户一定是同一个账户，而同名的账户却不一定是同一个账户，可以考虑对邮箱建立并查集，合并同属于一个账户的邮箱。

并查集

参考链接

一个带路径压缩的并查集实现如下

class UnionFind {
public:
    vector<int> parent;
    //初始化并查集，每个节点的父节点初始化为本身
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    //带路径压缩的合并，把index2合并到集合index1上
    //注：具体的合并规则由自己决定
    void unionSet(int index1, int index2) { 
       //把index2的父节点的父节点设置为index1的父节点，路径压缩
        parent[find(index2)] = find(index1);
    }
    
    //带路径压缩的查找，查找index对应的父节点
    int find(int index) {
        if (parent[index] != index) {
            //递归查找直到找到index的根节点
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
};

题目代码详解

实现并查集

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    void unionSet(int index1, int index2) { //把index2合并到index1
        parent[find(index2)] = find(index1);
    }

    int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);    //路径压缩
        }
        return parent[index];
    }
};

初始化

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        map<string, int> emailToIndex;	//建立email列表
        map<string, string> emailToName;//建立email和姓名映射
        int emailsCount = 0;

        //初始化并查集
        for (auto& account : accounts) {
            string& name = account[0];
            int size = account.size();
            for (int i = 1; i < size; i++) {
                string& email = account[i];
                if (!emailToIndex.count(email)) {   //去除重复邮箱，将新邮箱加入邮箱list
                    emailToIndex[email] = emailsCount++;    //建立邮箱和index映射
                    emailToName[email] = name;	//建立邮箱和姓名的映射
                }
            }
        }
        UnionFind uf(emailsCount);  //初始化并查集大小为email的个数
};

合并邮箱索引

//循环中把每个账户的email合并到一个email中
        for (auto& account : accounts) {
            string& firstEmail = account[1];//当前账户第一个邮箱
            int firstIndex = emailToIndex[firstEmail];//获取第一个邮箱的索引
            int size = account.size();  //统计当前账户邮箱个数
            //将当前账户的的每一个邮箱都合并到第一个邮箱
            //每个账户的邮箱一定属于同一个集合
            //而在不同账户里的重复邮箱已经合并到其根节点(压缩路径，递归查找)
            //所以不同账户里的邮箱都可以合并到同一个集合
            for (int i = 2; i < size; i++) {	
                string& nextEmail = account[i];
                int nextIndex = emailToIndex[nextEmail];
                //当前账户的email一定属于一个集合
                uf.unionSet(firstIndex, nextIndex); //合并当前账户第一个和其他邮箱
            }
        }

对于一个账户之中邮箱合并方式如图

对于不同账户之间的合并，并查集实现如下。如图由于节点9已经归属于节点20，当需要节点9合并到节点12时，只需要把节点20（9的根节点）合并到12即可。

转换为账户

map<int, vector<string>> indexToEmails;	//将合并后的索引映射到email
        for (auto& [email, _] : emailToIndex) { //for k v in map
            int index = uf.find(emailToIndex[email]);   //找到当前email的父节点
            vector<string>& account = indexToEmails[index];
            account.emplace_back(email);    //在account后追加email
            indexToEmails[index] = account; //拼接出同属于一个父节点的emails
        }

遍历emailToindex依照并查集合并后的结果把email追加在indexToEmails后面。

拼接账户

        //对合并好之后的账户进行排序拼接
        vector<vector<string>> merged;
        for (auto& [_, emails] : indexToEmails) {   //for k v in map
            sort(emails.begin(), emails.end()); //对emails里的元素进行排序
            string& name = emailToName[emails[0]];  //找到属于email的对应名字
            vector<string> account;
            //拼接成一个account
            account.emplace_back(name);
            for (auto& email : emails) {
                account.emplace_back(email);
            }
            //将account拼接成账户
            merged.emplace_back(account);
        }
        return merged;

完整实现

leetcode中文社区官方题解代码如下

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    void unionSet(int index1, int index2) { //把index2合并到index1
        parent[find(index2)] = find(index1);
    }

    int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);    //路径压缩
        }
        return parent[index];
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        map<string, int> emailToIndex;
        map<string, string> emailToName;
        int emailsCount = 0;
        for (auto& account : accounts) {
            string& name = account[0];
            int size = account.size();
            for (int i = 1; i < size; i++) {
                string& email = account[i];
                if (!emailToIndex.count(email)) {
                    emailToIndex[email] = emailsCount++;
                    emailToName[email] = name;
                }
            }
        }
        UnionFind uf(emailsCount);  
        for (auto& account : accounts) {
            string& firstEmail = account[1];
            int firstIndex = emailToIndex[firstEmail];
            int size = account.size();
            for (int i = 2; i < size; i++) {
                string& nextEmail = account[i];
                int nextIndex = emailToIndex[nextEmail];
                uf.unionSet(firstIndex, nextIndex);
            }
        }
        map<int, vector<string>> indexToEmails;
        for (auto& [email, _] : emailToIndex) {
            int index = uf.find(emailToIndex[email]);
            vector<string>& account = indexToEmails[index];
            account.emplace_back(email);
            indexToEmails[index] = account;
        }
        vector<vector<string>> merged;
        for (auto& [_, emails] : indexToEmails) {
            sort(emails.begin(), emails.end());
            string& name = emailToName[emails[0]];
            vector<string> account;
            account.emplace_back(name);
            for (auto& email : emails) {
                account.emplace_back(email);
            }
            merged.emplace_back(account);
        }
        return merged;
    }
};