LeetCode 721. 账户合并

2026-03-18 HGNULB 约 17 分钟

文章信息 7 个分类 7 个标签

分类

题目描述

✅ 721. 账户合并

题意分析

给一批账户，每个账户是一个列表：第 0 个元素是用户名，其余元素是该账户下的邮箱。规则是——只要两个账户共享至少一个邮箱，它们就属于同一个人，需要合并；同名但没有共享邮箱的账户则属于不同的人，不能合并。输出合并后的账户列表，每一条是「用户名 + 该人全部邮箱的升序去重列表」，账户之间的顺序任意。

要什么：把账户划分成若干组，然后对每组做邮箱的并集、去重、排序。所以这道题天然是两个阶段：先定分组，再组装输出，两个阶段的逻辑不应该纠缠在一起。

题面最关键的一句话是「同名不代表同人，共享邮箱才代表同人」。这直接排除了「按名字分组」这条捷径，也说明名字在合并阶段完全不参与判断，只在最后拼输出时用一次。

更重要的是合并关系具有传递性：账户 A 和 B 共享邮箱、B 和 C 共享另一个邮箱，那么 A、B、C 三者必须合并成一个人，即便 A 和 C 之间毫无交集。传递闭包 + 动态合并，这两个词合起来几乎就是并查集的定义式描述；用 DFS/BFS 在「账户-邮箱」二分图上求连通分量也等价，但并查集的实现更短、更不容易写崩。

约束透露的信号：账户数最多 1000，每个账户最多 10 个邮箱，所以邮箱总数 $m$ 在 $10^4$ 量级。这个规模下 $O(m \log m)$ 的排序是主要开销，并查集那点近似常数的操作可以忽略。反过来，$O(n^2)$ 地两两比较账户求交集（$10^6$ 次集合求交）虽然勉强能过，但既慢又完全没利用传递性，是应当被否掉的方向。

边界：同一个账户内部可能重复列出同一个邮箱，去重必须做；不同的人可以重名，输出里出现两条同名记录是正常的；某个账户的邮箱可能只属于它自己，它单独成一组；输出顺序不作要求，但每组内的邮箱必须严格升序。

解法：并查集按邮箱建立账户关系

核心思路

先看暴力：把每个账户的邮箱装进一个集合，两两账户求交集，有交集就合并成一个新账户，然后重新再来一轮，直到某一轮不再发生任何合并为止。这个做法要处理「合并后可能触发新的合并」，外层轮数最坏是 $O(n)$，每轮 $O(n^2)$ 次集合求交，总量不可接受。瓶颈在于：传递性被当作需要反复迭代才能收敛的东西来处理，而不是被一次性地表达出来。

换个角度，把每个账户看成图中的一个节点。「共享邮箱」定义了节点之间的边，那么「属于同一个人」就等价于「在同一个连通分量里」，传递性天然被连通性包含。于是问题变成：求账户图的连通分量，再按分量聚合邮箱。

但边不能真的两两枚举去建。这里用一个关键技巧：用邮箱做中介，把「共享」转化为增量的 union。维护一张哈希表 owner: 邮箱 → 首次见到该邮箱的账户下标。遍历所有账户的所有邮箱，遇到一个邮箱时——若表里没有，就登记为「这个邮箱归 i 所有」；若表里已有 prev，说明账户 i 与账户 prev 共享了它，执行 union(i, prev)。

这一步的正确性需要一句论证：某个邮箱若出现在账户 $a_1, a_2, \dots, a_t$ 中（按遍历顺序），代码只连了 $t - 1$ 条边 $(a_2, a_1), (a_3, a_1), \dots$，而不是全部 $\binom{t}{2}$ 条。但连通性只需要一棵生成树——把它们全部挂到 $a_1$ 上，已经保证这 $t$ 个账户处于同一个分量，多余的边不改变连通结果。这把建图的代价从 $O(m^2)$ 降到 $O(m)$。

并查集本身用路径压缩 + 按大小合并两个优化，单次操作的均摊代价是反阿克曼函数 $\alpha(n)$，实践中小于 5，可视作常数。

第二阶段严格与第一阶段分离。此时再遍历一次 owner 表，对每个 (邮箱, 首次账户) 求 find(首次账户) 拿到最终的根，把邮箱塞进 根 → 邮箱集合 的映射里。这里必须重新 find 而不能沿用登记时的下标——登记发生在合并过程中，那个下标当时是不是根、后来有没有被并到别处，都无从保证；只有全部 union 结束后调用的 find 才给出稳定的分量代表元。

邮箱容器选 TreeSet（Go 用 map 去重后 sort.Strings），一次性解决去重与升序两件事。最后每组取根账户的名字拼在最前面——同一分量里所有账户必然同名，取哪个都一样，取根最省事。

解题步骤

建一个大小为账户数 n 的并查集，节点是账户下标而非邮箱。为什么以账户为节点：题目要合并的单位是账户，最终每组要输出一个名字，而名字挂在账户上；若以邮箱为节点，还得额外维护「邮箱 → 名字」的映射，反而绕。

遍历每个账户 i，内层从下标 1 开始遍历邮箱。为什么从 1 而不是 0：下标 0 是用户名不是邮箱，把它当邮箱塞进 owner 会让所有同名账户被错误地合并到一起。

owner 里没有该邮箱就登记 owner[email] = i，已有 prev 就执行 union(i, prev)。为什么已有时不更新 owner：owner 的语义是「该邮箱的代表账户」，保持首次登记者不变就能让所有共享者都连向同一个中心，形成星形而非链形，边数最少。

第一阶段结束后再开始第二阶段。为什么必须分离：合并过程中任意时刻的 find 结果都可能被后续 union 改写；只有全部边加完，根才稳定下来。把组装写进第一阶段的循环里，是这题最典型的结构性错误。

遍历 owner 的每一项，用 find(value) 求根，把 key 加进 groups[root] 这个 TreeSet。为什么遍历 owner 而不是重新遍历 accounts：owner 的键集合已经是全体邮箱的去重结果，天然避免了同一邮箱被处理多次；用 TreeSet 则同时拿到组内去重与升序。

对每个分量，取 accounts.get(root).get(0) 作为名字，后接排好序的邮箱列表。为什么可以任取分量内一个账户的名字：能被合并的账户必然属于同一个人，题目保证它们同名；根是现成的、唯一的代表。

并查集的 find 用两趟循环实现路径压缩：第一趟一路向上找到 root，第二趟再走一遍把沿途每个节点的 parent 直接指向 root。为什么不用递归：账户数虽只有 1000，但迭代版没有栈深风险，且两趟循环的常数很小。

union 里先比 size 再挂靠，小树挂到大树上。为什么：按大小合并把树高控制在 $O(\log n)$，与路径压缩叠加后单次操作均摊 $O(\alpha(n))$；若无脑写 parent[ra] = rb，最坏会退化成一条长链。

以 具体用例 走一遍：
accounts = [
  ["John", "johnsmith@mail.com", "john_newyork@mail.com"],   // 下标 0
  ["John", "johnsmith@mail.com", "john00@mail.com"],         // 下标 1
  ["Mary", "mary@mail.com"],                                 // 下标 2
  ["John", "johnnybravo@mail.com"]                           // 下标 3
]
预期结果是三组：账户 0 与 1 因共享 johnsmith@mail.com 合并；账户 2 单独一组；账户 3 虽然也叫 John，但没有任何共享邮箱，必须单独一组。

第一阶段（建关系），初始 parent = [0,1,2,3]，size = [1,1,1,1]，owner = {}。
账户 0 的 johnsmith@mail.com：owner 中没有，登记 → 0。
账户 0 的 john_newyork@mail.com：没有，登记 → 0。
账户 1 的 johnsmith@mail.com：已存在，prev = 0，执行 union(1, 0)。find(1) = 1，find(0) = 0，两根不同；size[1] = 1 不小于 size[0] = 1，不交换，于是 parent[0] = 1，size[1] = 2。注意此处 owner["johnsmith@mail.com"] 仍然保持 0 不变。
账户 1 的 john00@mail.com：没有，登记 → 1。
账户 2 的 mary@mail.com：没有，登记 → 2。
账户 3 的 johnnybravo@mail.com：没有，登记 → 3。
第一阶段结束，parent = [1,1,2,3]，owner 共 5 项。

第二阶段（按根聚合），遍历 owner：
johnsmith@mail.com → 0，find(0)：parent[0] = 1、parent[1] = 1，根是 1，同时路径压缩把 parent[0] 直接指向 1（本例中它已经是 1）。加入 groups[1]。这一步正是「必须重新 find」的体现——登记时记的是 0，但 0 早已不是根了。
john_newyork@mail.com → 0，根同样是 1，加入 groups[1]。
john00@mail.com → 1，根是 1，加入 groups[1]。
mary@mail.com → 2，根是 2，加入 groups[2]。
johnnybravo@mail.com → 3，根是 3，加入 groups[3]。
得到 groups = { 1: {john00@mail.com, john_newyork@mail.com, johnsmith@mail.com}, 2: {mary@mail.com}, 3: {johnnybravo@mail.com} }。TreeSet 已按字典序排好，注意 john00 里的字符 0（ASCII 48）小于 _（95）也小于 s（115），所以顺序是 john00 < john_newyork < johnsmith。

组装输出：
根 1 → 名字取 accounts[1][0] = "John"，输出 ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"]。
根 2 → ["Mary","mary@mail.com"]。
根 3 → ["John","johnnybravo@mail.com"]。
三条记录中有两条叫 John，这是正确的：同名但无共享邮箱的人必须分开。

代码实现

class Solution {
    // 一旦用并查集把共享邮箱对应的账户合并，问题就从字符串匹配变成了聚合每个连通分量里的邮箱集合。
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        DSU dsu = new DSU(n);
        Map<String, Integer> owner = new HashMap<>();

        for (int i = 0; i < n; i++) {
            List<String> account = accounts.get(i);
            for (int j = 1; j < account.size(); j++) {
                String email = account.get(j);
                Integer prev = owner.get(email);
                if (prev == null) {
                    owner.put(email, i);
                } else {
                    dsu.union(i, prev);
                }
            }
        }

        Map<Integer, TreeSet<String>> groups = new HashMap<>();
        for (Map.Entry<String, Integer> entry : owner.entrySet()) {
            int root = dsu.find(entry.getValue());
            groups.computeIfAbsent(root, k -> new TreeSet<>()).add(entry.getKey());
        }

        List<List<String>> answer = new ArrayList<>();
        for (Map.Entry<Integer, TreeSet<String>> entry : groups.entrySet()) {
            List<String> row = new ArrayList<>();
            row.add(accounts.get(entry.getKey()).get(0));
            row.addAll(entry.getValue());
            answer.add(row);
        }
        return answer;
    }

    private static class DSU {
        private final int[] parent;
        private final int[] size;

        DSU(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            int root = x;
            while (parent[root] != root) {
                root = parent[root];
            }
            while (parent[x] != x) {
                int p = parent[x];
                parent[x] = root;
                x = p;
            }
            return root;
        }

        void union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return;
            }
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
}

type DSU struct {
    // 一旦用并查集把共享邮箱对应的账户合并，问题就从字符串匹配变成了聚合每个连通分量里的邮箱集合。
    parent []int
    size   []int
}

func newDSU(n int) *DSU {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &DSU{parent: parent, size: size}
}

func (d *DSU) find(x int) int {
    root := x
    for d.parent[root] != root {
        root = d.parent[root]
    }
    for d.parent[x] != x {
        p := d.parent[x]
        d.parent[x] = root
        x = p
    }
    return root
}

func (d *DSU) union(a, b int) {
    ra := d.find(a)
    rb := d.find(b)
    if ra == rb {
        return
    }
    if d.size[ra] < d.size[rb] {
        ra, rb = rb, ra
    }
    d.parent[rb] = ra
    d.size[ra] += d.size[rb]
}

type StringSet map[string]struct{}

func accountsMerge(accounts [][]string) [][]string {
    n := len(accounts)
    dsu := newDSU(n)
    owner := make(map[string]int)

    for i := 0; i < n; i++ {
        for j := 1; j < len(accounts[i]); j++ {
            email := accounts[i][j]
            if prev, ok := owner[email]; ok {
                dsu.union(i, prev)
            } else {
                owner[email] = i
            }
        }
    }

    groups := make(map[int]StringSet)
    for email, idx := range owner {
        root := dsu.find(idx)
        set, ok := groups[root]
        if !ok {
            set = make(StringSet)
            groups[root] = set
        }
        set[email] = struct{}{}
    }

    answer := make([][]string, 0, len(groups))
    for root, set := range groups {
        emails := make([]string, 0, len(set))
        for email := range set {
            emails = append(emails, email)
        }
        sort.Strings(emails)
        row := make([]string, 0, len(emails)+1)
        row = append(row, accounts[root][0])
        row = append(row, emails...)
        answer = append(answer, row)
    }
    return answer
}

复杂度分析

时间复杂度：$O(m \log m \cdot L)$，其中 $m$ 是邮箱总数、$L$ 是邮箱平均长度。凭什么：第一阶段对每个邮箱做一次哈希查询与至多一次 union，并查集在路径压缩加按大小合并下单次均摊 $O(\alpha(n))$（$\alpha$ 是反阿克曼函数，实践中小于 5），这一阶段是 $O(m \cdot L)$（哈希与字符串比较要按长度计）；第二阶段把 $m$ 个邮箱插入 TreeSet，每次插入是 $O(\log m)$ 次字符串比较，构成主要开销。排序才是复杂度瓶颈，并查集不是——这是本题复杂度分析里最该说清的一点。

空间复杂度：$O(m \cdot L)$。凭什么：owner 存了全部 $m$ 个不同邮箱的键，groups 里所有 TreeSet 加起来同样是 $m$ 个字符串引用，两者同阶；并查集只占 $O(n)$，$n \le m$，可被吸收。输出本身也是 $O(m \cdot L)$，属于必需开销。

关键点总结

「关系具有传递性 + 关系是动态增加的」是并查集的识别信号。一旦看到「A 和 B 是一伙的，B 和 C 是一伙的，所以 A 和 C 也是一伙的」，就该停止两两比较的思路，转向连通分量。

用中介物把「共享」转成 union，避免 $O(m^2)$ 建边。维护「特征 → 首个拥有者」的哈希表，后来者只与首个拥有者连一条边，形成星形结构。连通性只需生成树，不需要完全图——这个观察在「相同字符串组」「按属性分组」一类题里可以直接复用。

合并阶段与组装阶段必须严格分离，且组装时要重新 find。合并进行中的任何 find 结果都是临时的；只有全部 union 完成后的根才是稳定的分量标识。把两阶段写在一起是这题最高频的结构性错误。

让容器一次性承担「去重 + 排序」两件事。用 TreeSet（或先 map 去重再 sort）比「先收集成 List、再手工去重、再排序」更短也更不易错，同时天然处理了「同一账户内重复列出同一邮箱」这个边界。

并查集的两个优化要一起上：路径压缩负责把树压扁，按大小（或按秩）合并负责防止长链生成。只写其中之一在极端数据下仍可能退化，两者叠加才是均摊 $O(\alpha(n))$。

面试视角：面试官问这题，会重点确认三件事——你有没有意识到「同名不等于同人」、有没有用中介邮箱避免两两建边、以及有没有把组装阶段的 find 放在所有 union 之后。写完后主动补一句「也可以把账户和邮箱一起当作图的节点跑 DFS 求连通分量，复杂度相同，但并查集的代码量和出错面更小」，能体现你对两条路线都清楚。此外，被追问复杂度时务必指出瓶颈在排序而非并查集，这是区分「背过模板」和「真的分析过」的分水岭。

易错点总结

错误写法：内层循环从 j = 0 开始 → 用例中账户 0 和账户 3 都叫 "John"，名字被当成邮箱塞进 owner，第二次遇到时触发 union，两个毫无共享邮箱的人被错误合并成一组，输出少一条记录。

错误写法：在第一阶段的循环里就调用 find 并把邮箱写进 groups → 用例 [["A","a"],["B","b"],["A","a","b"]]，处理账户 2 时账户 0 与 1 才刚被连起来，之前按旧根分好的组不会被追溯修正，最终输出成两组而不是正确的一组。

错误写法：第二阶段直接用 entry.getValue() 当组标识，不调用 find → 用例中 johnsmith@mail.com 登记的是账户 0，但 0 后来被并到 1 之下；不重新 find 就会把它单独归到「组 0」，与「组 1」里的其他邮箱割裂，一个人被拆成两条记录。

错误写法：遇到已存在的邮箱时顺手更新 owner[email] = i → 用例 [["A","x"],["A","x"],["A","x"]]，登记者不断被改写，虽然本例仍连通，但当某个邮箱在多个账户中出现时会连成一条链而非星形，配合缺失的按大小合并就可能退化；更糟的是若把更新写在 union 之前，还会丢失与最初账户的连接。

错误写法：用 List<String> 收集组内邮箱而不去重 → 用例 [["A","x","x","y"]]，同一账户内重复列出 x，输出会变成 ["A","x","x","y"]，与要求的去重结果不符。（本文的实现靠遍历 owner 的键天然规避了这点，但改写成遍历 accounts 时就必须自己去重。）

错误写法：忘记对组内邮箱排序 → 用例中组 1 若按哈希顺序输出 ["John","johnsmith@mail.com","john00@mail.com","john_newyork@mail.com"]，与要求的字典序不符，判题直接失败。

错误写法：按名字先分组再在组内做并查集 → 用例中两个 John 会落进同一个预分组，虽然并查集仍能把无共享邮箱的 John 分开，但这层多余的分组毫无收益；反过来若因此直接把同名账户 union，则会把账户 0 和账户 3 错误合并。

错误写法：union 里写成 parent[a] = b（用原下标而非根） → 用例 [["A","1"],["A","1","2"],["A","2","3"]]，把非根节点的父指针直接改掉会切断它原来所在子树与真正根的联系，find 返回错误的代表元，分组结果随机出错。

错误写法：find 只写向上找根、不做路径压缩，同时 union 也不按大小合并 → 用例是 1000 个账户串成一条共享链时，树退化成长度 1000 的链，每次 find 都是 $O(n)$，总复杂度从近似线性劣化到 $O(nm)$。

错误写法：把并查集的节点定义成邮箱（用字符串做键）却忘了给每个邮箱关联名字 → 组装阶段无从得知该分量属于谁，只能回头再扫一遍 accounts 建反向映射，白白多一轮 $O(m)$ 且代码复杂度陡增；以账户为节点可以直接 accounts[root][0] 取名。

错误写法：Go 中 groups[root] 取出的 map 未判空就直接写入 → 用例任意，对 nil map 赋值会 panic；必须先用逗号 ok 判断并在缺失时 make 一个新集合再放回。

相似题目

题目	难度	考察点
547. 省份数量	中等	邻接矩阵直接给出边，只需数分量个数，不涉及分量内部的聚合与排序
323. 无向图中连通分量的数目	中等	边以列表形式直接给出，是并查集最裸的形态，可用「初始分量数减去有效合并次数」
684. 冗余连接	中等	关注的是 union 失败的那一刻，即两端已连通说明这条边成环
990. 等式方程的可满足性	中等	必须先处理全部等式再校验不等式，与本题「先合并后组装」的分阶段思想同源
839. 相似字符串组	困难	边需要 $O(n^2)$ 两两判定相似性，无法用中介物省去建边，与本题形成对照
1202. 交换字符串中的元素	中等	分量内部要对字符排序后按下标回填，组装阶段比本题更讲究位置对应
765. 情侣牵手	困难	答案是「节点数减去分量数」，考的是把最少交换次数转化为分量结构的结论
128. 最长连续序列	中等	也可用并查集按数值相邻合并并取最大分量规模，但哈希表跳跃扫描是更优解
1319. 连通网络的操作次数	中等	需要同时统计冗余边数与分量数，并先判断线缆是否足够
面试题 17.07. 婴儿名字	中等	与本题最接近的变体，分量代表元要取字典序最小的名字而非任取
LCR 116. 省份数量	中等	与 547 同题，可直接套用
LCR 118. 冗余连接	中等	与 684 同题，可直接套用