721. 账户合并 ●●、并查集

721. 账户合并 ●●

描述

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

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

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

示例

输入：
[[“David”,“[email protected]”,“[email protected]”],[“David”,“[email protected]”,“[email protected]”],[“David”,“[email protected]”,“[email protected]”],[“David”,“[email protected]”,“[email protected]”],[“David”,“[email protected]”,“[email protected]”]]
输出：
[[“David”,“[email protected]”,“[email protected]”,“[email protected]”,“[email protected]”,“[email protected]”,“[email protected]”]]

题解

1. 无脑暴力

通过哈希表记录 重复的邮箱 以及 处理过的下标 进行无脑暴力合并，直到一次遍历之后不发生合并操作（即遍历前后人数相等）为止，最后对字符串进行排序。

class Solution {
    
public:
    vector<vector<string>> doMerge(vector<vector<string>>& accounts){
    
        unordered_set<string> emap;
        int n = accounts.size();
        unordered_set<int> hash;
        vector<vector<string>> ans;
        for(int i = 0; i < n; ++i){
    
            if(hash.count(i) == 0){
                                         // 该下标未处理过
                emap.clear();
                string name = accounts[i][0];
                ans.emplace_back(vector<string>());
                ans.back().emplace_back(name);
                for(int j = 1; j < accounts[i].size(); ++j){
                // 当前地址加入数组 和 哈希表
                    if(emap.count(accounts[i][j]) == 0){
                    // 邮件地址去重
                        emap.insert(accounts[i][j]);
                        ans.back().emplace_back(accounts[i][j]);
                    }
                }       
                for(int k = i+1; k < n; ++k){
    
                    if(hash.count(k) == 0 && accounts[k][0] == name){
       // 同名
                        for(int j = 1; j < accounts[k].size(); ++j){
        // 遍历邮件地址
                            if(emap.count(accounts[k][j]) > 0){
             // 同人
                                hash.insert(k);                         // 处理小标 k
                                for(int h = 1; h < accounts[k].size(); ++h){
    
                                    if(emap.count(accounts[k][h]) == 0){
    // 邮件地址去重
                                        ans.back().emplace_back(accounts[k][h]);
                                        emap.insert(accounts[k][h]);
                                    }  
                                }
                                break;                                  // 跳出邮件遍历，处理下一个人
                            }
                        }
                    }
                }

            }
        }
        return ans;
    }

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    
        int pre = accounts.size();
        while(true){
    
            accounts = doMerge(accounts);
            if(accounts.size() == pre) break;            // 人数相等，当前循环未发生合并
            pre = accounts.size();
        }
        for(int i = 0; i < accounts.size(); ++i){
    
            sort(accounts[i].begin()+1, accounts[i].end());
        }
        return accounts;
    }
};

2. 哈希表 + 并查集

并查集详解

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。

并查集通常包含两种操作

• 查找(Find)：查询两个元素是否在同一个集合中（相同的根节点）
• 合并(Union)：把两个不相交的集合合并为一个集合

并查集类通用模板：

//并查集类
class DisJointSetUnion
{
    
private:
    // 所有根结点相同的结点位于同一个集合中
    vector<int> parent;    // 双亲结点数组，记录该结点的双亲结点，用于查找该结点的根结点
    vector<int> rank;      // 秩数组，记录以该结点为根结点的树的深度，主要用于优化，在合并两个集合的时候，rank大的集合合并rank小的集合

public:
    DisJointSetUnion(int n){
              //构造函数
        for (int i = 0; i < n; i++){
    
            parent.push_back(i);      //此时各自为王，自己就是一个集合
            rank.push_back(1);        //rank = 1，此时每个结点自己就是一颗深度为1的树
        }
    }

    //查找根结点
    int find(int x){
    
        if(parent[x] != x){
    
            parent[x] = find(parent[x]);   // 路径压缩， 遍历过程中的所有双亲结点直接指向根结点，减少后续查找次数
        }
        return parent[x];
    }

    void merge(int x,int y)
    {
    
    	// parent[find(y)] = find(x); // 不是用按秩合并时，直接将 y 所在集合 合并到 x 所在的集合中
    	
        int rx = find(x);                 // 查找x的根结点，即x所在集合的代表元素
        int ry = find(y);
        if (rx != ry){
                        // 如果不是同一个集合
            if (rank[rx] < rank[ry]){
         // rank大的集合合并rank小的集合
                swap(rx, ry);             // 这里进行交换是为了保证 rank[rx] 大于等于 rank[ry]，方便下面合并
            }
            parent[ry] = rx;              //rx 合并 ry
            if (rank[rx] == rank[ry]) rank[rx] += 1;	// 更新树的深度，如果rank[rx] > rank[ry]，那么合并后rx深度不变
        }
    }
};

---

两个账户需要合并，当且仅当两个账户至少有一个共同的邮箱地址，因此这道题的实质是判断所有的邮箱地址中有哪些邮箱地址必定属于同一人，可以使用并查集实现。

为了使用并查集实现账户合并，需要知道一共有多少个不同的邮箱地址，以及每个邮箱对应的名称，因此需要使用两个哈希表分别记录每个邮箱对应的编号和每个邮箱对应的名称，遍历所有的账户并在两个哈希表中记录相应的信息。虽然同一个邮箱地址可能在多个账户中出现，但是同一个邮箱地址在两个哈希表中都只能存储一次。

然后使用并查集进行合并操作。由于同一个账户中的邮箱地址一定属于同一个人，因此遍历每个账户，对账户中的邮箱地址进行合并操作。并查集存储的是每个邮箱地址对应的编号，合并操作也是针对编号进行合并。

完成并查集的合并操作之后，即可知道合并后有多少个不同的账户。遍历所有的邮箱地址，对于每个邮箱地址，通过并查集得到该邮箱地址属于哪个合并后的账户，即可整理出每个合并后的账户包含哪些邮箱地址。

对于每个合并后的账户，需要整理出题目要求的返回账户的格式，具体做法是：将邮箱地址排序，账户的名称可以通过在哈希表中查找任意一个邮箱对应的名称得到，将名称和排序后的邮箱地址整理成一个账户列表。对所有合并后的账户整理出账户列表，即可得到最终答案。

• 时间复杂度：$O(n\log n)$，其中 nn 是不同邮箱地址的数量。
  – 需要遍历所有邮箱地址，在并查集内进行查找和合并操作，对于两个不同的邮箱地址，如果它们的祖先不同则需要进行合并，需要进行 2 次查找和最多 1 次合并。一共需要进行 2n 次查找和最多 n 次合并，因此时间复杂度是 $O(2n\log n)=O(n\log n)$。这里的并查集使用了路径压缩，但是没有使用按秩合并，最坏情况下的时间复杂度是 $O(n\log n)$，平均情况下的时间复杂度依然是$ O(n \alpha (n))$，其中 $\alpha$ 为阿克曼函数的反函数，$\alpha (n)$ 可以认为是一个很小的常数。
  – 整理出题目要求的返回账户的格式时需要对邮箱地址排序，时间复杂度是 $O(n\log n)$。
  – 其余操作包括遍历所有邮箱地址，在哈希表中记录相应的信息，时间复杂度是 O(n)，在渐进意义下 O(n) 小于 $O(n\log n)$。
  – 因此总时间复杂度是 $O(n\log n)$。

• 空间复杂度：$O(n)$，其中 n 是不同邮箱地址的数量。空间复杂度主要取决于哈希表和并查集，每个哈希表存储的邮箱地址的数量为 n，并查集的大小为 n。

class UnionFind{
    
public:
    vector<int> parent;     // 存放父节点下标

    UnionFind(int n){
           // 初始化大小为 n 的并查集
        parent.resize(n);
        for(int i = 0; i < n; ++i) parent[i] = i;
    }

    void unionSet(int idx1, int idx2){
              // 把 idx2 所在的集合 合并 到 idx1 所在集合中
        parent[find(idx2)] = find(idx1);
    }

    int find(int idx){
    
        if(parent[idx] != idx){
    
            parent[idx] = find(parent[idx]);    // 路径压缩，在查找过程中，同时更改父节点，使其直接指向根节点，减少后续查找次数
        }
        return parent[idx];
    }
};

class Solution {
    
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    
        unordered_map<string, int> emailToIdx;
        unordered_map<string, string> emailToName;
        int ecnt = 0;
        for(auto & account : accounts){
                 // 初始化 emailToIdx 和 emailToName
            string& name = account[0];
            int size = account.size();
            for(int i = 1; i < size; ++i){
    
                string& email = account[i];
                if(!emailToIdx.count(email)){
    
                    emailToIdx[email] = ecnt++;
                    emailToName[email] = name;
                }
            }
        }

        UnionFind uf(ecnt);                             // 一共有 ecnt 个不重复的邮箱
        for(auto& account : accounts){
    
            string& firstEmail = account[1];
            int firstIdx = emailToIdx[firstEmail];      // 第一个邮箱下标作为根节点
            int size = account.size();
            for(int i = 2; i < size; ++i){
    
                string& nextEmail = account[i];
                int nextIdx = emailToIdx[nextEmail];
                uf.unionSet(firstIdx, nextIdx);         // 把后面的邮箱所在的集合合并到第一个邮箱节点下
            }
        }

        unordered_map<int, vector<string>> idxToEmails; // 每个邮箱编号到邮箱集合的映射
        for(auto& [email, _] : emailToIdx){
                 // 遍历所有邮箱
            int idx = uf.find(emailToIdx[email]);       // 找到该邮箱的根节点
            vector<string>& account = idxToEmails[idx]; // 该根节点下的邮箱集合
            account.emplace_back(email);                // 合并邮箱
            idxToEmails[idx] = account;                 // 该节点下的邮箱集合映射
        }

        vector<vector<string>> merged;
        for(auto& [_, emails] : idxToEmails){
               // 遍历所有邮箱集合，多个 idx 对应 一个 Emails
            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;
    }
};

• 并查集 2

上一种方法把每个邮箱看过一个节点并进行连通，逻辑较复杂；

因此此处直接把每个初始账户数组看做一个集合节点并进行连通，具体的：

• 先初始化每个账户为 1 个连通分量，同时建立每个邮箱到集合根节点索引的映射
• 遍历每个账户下的邮箱，判断该邮箱是否在其他账户下出现
• 如果未出现，继续
• 如果账户A、B下出现了相同的邮箱 email，那么将账户A和账户B两个连通分量进行合并
• 遍历每个邮箱，将所有根节点相同的邮箱地址合并到同一个账户数组中
• 最后对每个账户数组进行邮箱地址排序

class UnionFind{
    
public:
    vector<int> parent;     // 存放父节点下标

    UnionFind(int n){
           // 初始化大小为 n 的并查集
        parent.resize(n);
        for(int i = 0; i < n; ++i) parent[i] = i;
    }

    void unionSet(int idx1, int idx2){
              // 把 idx2 所在的集合 合并 到 idx1 所在集合中
        parent[find(idx2)] = find(idx1);
    }

    int find(int idx){
    
        if(parent[idx] != idx){
    
            parent[idx] = find(parent[idx]);    // 路径压缩，在查找过程中，同时更改父节点，使其直接指向根节点，减少后续查找次数
        }
        return parent[idx];
    }
};


class Solution {
    
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    
        int n = accounts.size();
        UnionFind uf(n);                            // 把 accounts 每组元素作为一个集合
        unordered_map<string, int> emailToIdx;      // 每个邮箱到集合根节点索引的映射
        for(int i = 0; i < n; ++i){
    
            int size = accounts[i].size();      
            for(int j = 1; j < size; ++j){
              // 遍历每个邮箱
                string email = accounts[i][j];
                if(emailToIdx.find(email) == emailToIdx.end()){
         // 当前邮箱未遍历过，那么建立邮箱到根节点索引的映射
                    emailToIdx[email] = uf.find(i);                 // 根节点索引为 当前邮箱对应数组下标i 的根节点 uf.find(i)
                }else{
    
                    uf.unionSet(uf.find(emailToIdx[email]), i);     // 如果邮箱遍历过，那么代表重复，因此将当前集合合并到之前遍历过的集合中
                }
            }
        }
        
        vector<vector<string>> ret;
        unordered_map<int, int> findIdx;                            // 当前节点的头结点在新建数组ret中的位置
        int cnt = 0;
        for(auto& [email, idx] : emailToIdx){
                           // 遍历每个不重复的邮箱
            if(findIdx.find(uf.find(idx)) == findIdx.end()){
            // 当前节点的头结点还未创建账户
                ret.emplace_back();                                 // 创建账户
                ret.back().emplace_back(accounts[idx][0]);          // 邮箱对应的账户名
                ret.back().emplace_back(email);                     // 当前邮箱
                findIdx[uf.find(idx)] = cnt++;                      // 记录当前头结点对应的数组索引 
                
            }else{
    
                ret[findIdx[uf.find(idx)]].emplace_back(email);     // 直接将邮箱加入到头结点对应的账户中
            }
        }
        for(int i = 0; i < cnt; ++i){
    
            sort(ret[i].begin() + 1, ret[i].end());                 // 对每个账户信息进行排序
        }
        return ret;
    }
};