721-账户合并(Accounts Merge)

原文链接: https://leetcode-cn.com/problems/accounts-merge

英文原文

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Explanation:
The first and second John's are the same person as they have the common email "johnsmith@mail.com".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Example 2:

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
Output: [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

Constraints:

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j] <= 30
accounts[i][0] consists of English letters.
accounts[i][j] (for j > 0) is a valid email.

中文题目

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

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

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

示例 1：

输入：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']] 也是正确的。

示例 2：

输入：accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
输出：[["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

提示：

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] 由英文字母组成
accounts[i][j] (for j > 0) 是有效的邮箱地址

通过代码

高赞题解

方法一：并查集

1. 前言

如果您对【并查集】相关知识还不是太了解，可以看看我之前的题解【详解并查集】

有问题欢迎留言交流！

2. 解题思路

本题的题意比较直观，思路也比较清晰，可以使用【并查集】来解决。

根据题意可知：

存在相同邮箱的账号一定属于同一个人
名称相同的账户不一定属于同一个人

3. 思路

由于名称相同无法判断为同1人，所以只能使用邮箱是否相同来判断是否为同一人。

这样建立并查集就比较简单了：

先初始化每个账户为1个连通分量
遍历每个账户下的邮箱，判断该邮箱是否在其他账户下出现
如果未出现，继续
如果账户A、B下出现了相同的邮箱email，那么将账户A和账户B两个连通分量进行合并
最后遍历并查集中每个连通分量，将所有连通分量内部账户的邮箱全部合并(相同的去重，不同的合并)
结束

针对具体的实现，大家可以看看代码

4. 举例

5. 代码

class Djset {
public:
    vector<int> parent;  // 记录节点的根
    vector<int> rank;  // 记录根节点的深度（用于优化）
    Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        // 压缩方式：直接指向根节点
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
        }
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& acc) {
        vector<vector<string> > res;
        // 作用：存储每个邮箱属于哪个账户 ，同时 在遍历邮箱时，判断邮箱是否出现过
        // 格式：<邮箱，账户id>
        unordered_map<string, int> um;
        int n = acc.size();
        Djset ds(n);
        for (int i = 0; i < n; i++) {
            int m = acc[i].size();
            for (int j = 1; j < m; j++) {
                string s = acc[i][j];
                if (um.find(s) == um.end()) {
                    um[s] = i;
                } else {
                    ds.merge(i, um[s]);
                }
            }
        }
        // 作用： 存储每个账户下的邮箱
        // 格式： <账户id, 邮箱列表> >
        // 注意：这里的key必须是账户id，不能是账户名称，名称可能相同，会造成覆盖
        unordered_map<int, vector<string> > umv;
        for (auto& [k, v] : um) umv[ds.find(v)].emplace_back(k);
        for (auto& [k, v] : umv){
            sort(v.begin(), v.end());
            vector<string> tmp(1, acc[k][0]);
            tmp.insert(tmp.end(), v.begin(), v.end());
            res.emplace_back(tmp);
        } 


        return res;
    }
};

6. 总结

官方这个月强推【并查集】，不学会都不行！

一般针对可以使用并查集的题目，都可以直接使用并查集的模板或者稍微加以改造，并查集部分的代码不应该成为瓶颈。

普通的模板代码比较简单，但是一般效率比较低！

所以通常都会采用【路径压缩】和【按秩合并】两种优化方式，【模板代码】如下：

// 注意：使用该代码，并不能使得所有的元素都直接指向根节点，仍然存在间接指向
class Djset {
public:
    vector<int> parent;  // 记录节点的根
    vector<int> rank;    // 记录根节点的深度（用于优化）
    int count;           // 记录并查集的数量,某些情况下该成员非必要
    Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)), count(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        // 压缩方式：直接指向根节点
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void merge(int x, int y) {
        // 找到根节点
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            // 按秩合并
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            count--;
            // 如果秩相等，将父节点rootx秩 + 1
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
        }
    }
};

并查集的一些使用tips:

一般不会将并查集使用得太复杂，内部结构如果过于复杂，也难以维护

只负责维护连通性

存在区间合并的题干，应当考虑使用并查集

如果题干是拆分连通分量，反向思维，考虑逆向使用并查集

方法二：深度优先搜索/DFS

1. 解题思路

先对问题进行抽象，题目要求虽然是对账户进行合并，但终归结底是对账户下的所有邮箱进行合并。

另外题目也说了，相同账户的名称一定相同，所以用邮箱构建节点不会对账户造成任何影响。

所以比较简单的抽象方式是将每个邮箱当作一个节点来构建图（重复的邮箱算作同一个节点，这样避免最后输出重复），然后每个连通图表示一个账户，非连通图表示的是不同账户，也就是说，一个连通图里的所有节点（邮箱）属于同一个账户

2. 步骤

对数据进行预处理，给邮箱编号；
构建无向图，采用邻接表进行存储；
由于最后的结果图是由若干个连通图组成的非连通图，所以依次遍历每个连通图，同时输出该连通图里的所有邮箱。

3. 例子

图构建完之后，最后进行dfs即可。
关于dfs的相关知识，这里不作过多赘述！具体请看代码：

4. 代码

这里感谢@guoyuer指出的问题，具体见代码！

class Solution {
public:
    vector<vector<string> > res; // 结果集
    // map: 保存邮箱与编号的对应关系
    // 格式： <邮箱，编号>
    unordered_map<string, int> um; 
    // vector: 保存编号与邮箱的对应关系
    // 格式： <编号，邮箱>
    vector<string> mails; 

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        // 数据预处理：生成邮箱与编号的对应关系
        for (auto ac : accounts) {
            for (int i = 1; i < ac.size(); i++) {
                if (um.find(ac[i]) != um.end()) continue;
                mails.emplace_back(ac[i]);
                um[ac[i]] = mails.size() - 1;
            }
        }

        // 建图，邻接矩阵，存储相邻的邮箱编号
        int m = mails.size();
        vector<vector<int> > g(m);
        for (auto& ac : accounts) {
            for (int i = 1; i < ac.size(); i++) {
                for (int j = i + 1; j < ac.size(); j++) {
                    int idxI = um[ac[i]], idxJ = um[ac[j]];
                    g[idxI].push_back(idxJ);
                    g[idxJ].push_back(idxI);
                }
            }
        }

        // dfs
        vector<bool> visited(m);
        for (auto& ac : accounts) {
            vector<string> cur(1, ac[0]);
            if (ac.size() < 1) continue;
            if (!visited[um[ac[1]]]) {
                dfs(g, um[ac[1]], visited, cur);
                // 名称不参与排序，感谢 郭遇尔 指出！
                // sort(cur.begin(), cur.end());
                sort(cur.begin() + 1, cur.end());
                res.emplace_back(cur);
            }
        }
        return res;
    }

    void dfs(vector<vector<int> >& g, int idx, vector<bool>& visited, vector<string>& cur) {
        visited[idx] = true;
        cur.emplace_back(mails[idx]);
        for (auto& nei : g[idx]) {
            if (!visited[nei]) dfs(g, nei, visited, cur);
        }
    }
};

感谢您的观看，如有任何问题，欢迎留言交流！
若对您有帮助，希望不吝一赞 👍 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - \ by \ \ \ yex➰$

统计信息

通过次数	提交次数	AC比率
29973	63712	47.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
冗余连接	中等
句子相似性	简单
句子相似性 II	中等

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途