Medium

题目描述

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

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

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

示例 1：

输入: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
输出: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@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]（当 j > 0 时）是有效的邮箱地址

解题思路

这是一个典型的图连通分量问题。我们需要将属于同一个人的账户合并在一起。

解题思路：

核心思想是将每个邮箱看作图的节点，如果两个邮箱出现在同一个账户中，就在它们之间连边。最后找出所有的连通分量，每个连通分量就对应一个人的所有邮箱。

主要有两种解法：

  1. 并查集（Union-Find）：这是处理连通分量问题的经典方法。将同一账户中的邮箱进行合并操作，最后统计每个连通分量的所有邮箱。

  2. 深度优先搜索（DFS）：构建邮箱之间的邻接表，然后用DFS遍历每个连通分量。

推荐解法：并查集

  • 为每个邮箱分配一个唯一的ID
  • 遍历每个账户，将账户内的邮箱进行合并
  • 最后按照根节点分组，收集每个连通分量的所有邮箱
  • 对每组邮箱排序，并添加对应的姓名

这种方法时间复杂度相对较优，代码简洁易懂。

代码实现

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> emailToId;
        vector<string> emails;
        int id = 0;
        
        // 为每个邮箱分配唯一ID
        for (auto& account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                if (emailToId.find(account[i]) == emailToId.end()) {
                    emailToId[account[i]] = id++;
                    emails.push_back(account[i]);
                }
            }
        }
        
        // 并查集
        vector<int> parent(id);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        // 合并同一账户中的邮箱
        for (auto& account : accounts) {
            int firstEmailId = emailToId[account[1]];
            for (int i = 2; i < account.size(); i++) {
                int emailId = emailToId[account[i]];
                parent[find(emailId)] = find(firstEmailId);
            }
        }
        
        // 按根节点分组
        unordered_map<int, vector<string>> groups;
        unordered_map<string, string> emailToName;
        
        for (auto& account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                emailToName[account[i]] = account[0];
            }
        }
        
        for (int i = 0; i < id; i++) {
            groups[find(i)].push_back(emails[i]);
        }
        
        vector<vector<string>> result;
        for (auto& [root, emailList] : groups) {
            sort(emailList.begin(), emailList.end());
            vector<string> account;
            account.push_back(emailToName[emailList[0]]);
            account.insert(account.end(), emailList.begin(), emailList.end());
            result.push_back(account);
        }
        
        return result;
    }
};

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        email_to_id = {}
        emails = []
        
        # 为每个邮箱分配唯一ID
        for account in accounts:
            for email in account[1:]:
                if email not in email_to_id:
                    email_to_id[email] = len(emails)
                    emails.append(email)
        
        # 并查集
        parent = list(range(len(emails)))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # 合并同一账户中的邮箱
        for account in accounts:
            first_email_id = email_to_id[account[1]]
            for email in account[2:]:
                email_id = email_to_id[email]
                parent[find(email_id)] = find(first_email_id)
        
        # 按根节点分组
        groups = {}
        email_to_name = {}
        
        for account in accounts:
            for email in account[1:]:
                email_to_name[email] = account[0]
        
        for i in range(len(emails)):
            root = find(i)
            if root not in groups:
                groups[root] = []
            groups[root].append(emails[i])
        
        result = []
        for email_list in groups.values():
            email_list.sort()
            result.append([email_to_name[email_list[0]]] + email_list)
        
        return result

public class Solution {
    public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
        var emailToId = new Dictionary<string, int>();
        var emails = new List<string>();
        int id = 0;
        
        // 为每个邮箱分配唯一ID
        foreach (var account in accounts) {
            for (int i = 1; i < account.Count; i++) {
                if (!emailToId.ContainsKey(account[i])) {
                    emailToId[account[i]] = id++;
                    emails.Add(account[i]);
                }
            }
        }
        
        // 并查集
        var parent = new int[id];
        for (int i = 0; i < id; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        // 合并同一账户中的邮箱
        foreach (var account in accounts) {
            int firstEmailId = emailToId[account[1]];
            for (int i = 2; i < account.Count; i++) {
                int emailId = emailToId[account[i]];
                parent[Find(emailId)] = Find(firstEmailId);
            }
        }
        
        // 按根节点分组
        var groups = new Dictionary<int, List<string>>();
        var emailToName = new Dictionary<string, string>();
        
        foreach (var account in accounts) {
            for (int i = 1; i < account.Count; i++) {
                emailToName[account[i]] = account[0];
            }
        }
        
        for (int i = 0; i < id; i++) {
            int root = Find(i);
            if (!groups.ContainsKey(root)) {
                groups[root] = new List<string>();
            }
            groups[root].Add(emails[i]);
        }
        
        var result = new List<IList<string>>();
        foreach (var emailList in groups.Values) {
            emailList.Sort();
            var account = new List<string> { emailToName[emailList[0]] };
            account.AddRange(emailList);
            result.Add(account);
        }
        
        return result;
    }
}

var accountsMerge = function(accounts) {
    const emailToId = new Map();
    const emails = [];
    let id = 0;
    
    // 为每个邮箱分配唯一ID
    for (const account of accounts) {
        for (let i = 1; i < account.length; i++) {
            if (!emailToId.has(account[i])) {
                emailToId.set(account[i], id++);
                emails.push(account[i]);
            }
        }
    }
    
    // 并查集
    const parent = Array.from({length: id}, (_, i) => i);
    
    function find(x) {
        return parent[x]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型并查集解法
时间复杂度O(N × M × α(N × M) + N × M × log(N × M))
空间复杂度O(N × M)

其中：

  • N 是账户数量
  • M 是每个账户的平均邮箱数量
  • α 是阿克曼函数的反函数，在实际应用中可视为常数
  • 时间复杂度主要由并查集操作和排序组成
  • 空间复杂度主要用于存储邮箱映射和并查集数组

相关题目