LeetCode 面试题 17.07. 婴儿名字

2022-07-18 HGNULB 约 7 分钟

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

分类

LeetCode CodeTop 中等未解决 2-5 程序员面试金典（第 6 版）腾讯快手

题目描述

✅ 面试题 17.07. 婴儿名字

题意分析

同义名字具有对称性和传递性，需要把同一组所有名字的频次相加，并以组内字典序最小的名字输出。仅出现在同义关系中、没有频次记录的名字也属于该组，可以参与连接和代表名选择，只是不增加频次。

解法：并查集合并同义词

核心思路

[!blue]

把每个名字看成一个元素，同义关系就是将两个元素所在的集合合并。并查集的 parent 保存父名字，父名字等于自己时是根；find 沿父链接找到根，同根就代表两个名字已经通过直接或间接关系连通。

首次遇到名字时，把它登记为独立集合。合并两个名字时，必须先找到两个根；若已同根就不再修改，否则将字典序较大的根接到较小的根。单元素集合的根就是自身，而两个集合合并后，较小的旧根也是合并集合的最小名字，因此这个规则始终让根保持组内最小，不需要额外扫描组成员来选代表。

查找过程中还会缩短父链。Java 将当前节点直接接到祖父节点，再继续向上查找，用迭代避免按字典序合并形成长链时递归栈溢出；Go 在递归回溯时将沿途节点接到最终根。压缩只跳过同一组内部的祖先，不改变集合归属或代表名字。

先完成全部同义关系，再聚合频次。遍历原频次表，对每个名字查找最终根，将频次加到 sumMap[root]。这样每条原记录只计入一个最终分组，不会因为后面代表改变而把同组频次拆开。没有同义关系的名字会在这一步登记，独立保留自己的频次。

最后把非零总频次格式化为 名字(频次)。关系中独有的名字可以成为根，但没有任何频次记录的分组不会产生输出；代表名是组内最小，并不意味着不同分组的输出顺序也经过排序。

解题步骤

解析 names，建立名字到频次的映射。

解析每组 synonyms，为尚未见过的名字建集合，再合并两个根。

所有关系处理完后，遍历频次表，按最终根汇总频次。

跳过总频次为零的分组，输出代表名字及其合计频次。

代码实现

// 同义名字合并并选字典序最小代表，返回数组本身不保证排序。
class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> countMap = new HashMap<>();

        for (String item : names) {
            int left = item.indexOf('(');
            int right = item.indexOf(')');
            String name = item.substring(0, left);
            int count = Integer.parseInt(item.substring(left + 1, right));

            countMap.put(name, count);
        }

        UnionFind uf = new UnionFind();

        for (String pair : synonyms) {
            int comma = pair.indexOf(',');
            String a = pair.substring(1, comma);
            String b = pair.substring(comma + 1, pair.length() - 1);

            uf.union(a, b);
        }

        Map<String, Integer> sumMap = new HashMap<>();

        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            // 所有关系完成后再按最终代表聚合频次。
            String root = uf.find(entry.getKey());

            sumMap.put(root, sumMap.getOrDefault(root, 0) + entry.getValue());
        }

        List<String> res = new ArrayList<>();

        for (Map.Entry<String, Integer> entry : sumMap.entrySet()) {
            if (entry.getValue() == 0) {
                continue;
            }

            res.add(entry.getKey() + "(" + entry.getValue() + ")");
        }

        return res.toArray(new String[0]);
    }

    static class UnionFind {
        private final Map<String, String> parent = new HashMap<>();

        String find(String x) {
            // 同义关系中独有的名字也要登记，才能参与连通与代表选择。
            parent.putIfAbsent(x, x);

            while (!parent.get(x).equals(x)) {
                parent.put(x, parent.get(parent.get(x)));
                x = parent.get(x);
            }

            return x;
        }

        void union(String a, String b) {
            String pa = find(a);
            String pb = find(b);

            if (pa.equals(pb)) {
                return;
            }

            // 连接两个代表根，字典序较小者成为新代表。
            if (pa.compareTo(pb) < 0) {
                parent.put(pb, pa);
            } else {
                parent.put(pa, pb);
            }
        }
    }
}

import (
    "fmt"
    "strconv"
    "strings"
)

// 同义名字合并并选字典序最小代表，返回数组本身不保证排序。
func trulyMostPopular(names []string, synonyms []string) []string {
    countMap := map[string]int{}
    for _, item := range names {
        left := strings.IndexByte(item, '(')
        right := strings.IndexByte(item, ')')
        name := item[:left]
        cnt, _ := strconv.Atoi(item[left+1 : right])
        countMap[name] = cnt
    }

    uf := newUnionFind()
    for _, pair := range synonyms {
        comma := strings.IndexByte(pair, ',')
        a := pair[1:comma]
        b := pair[comma+1 : len(pair)-1]
        uf.union(a, b)
    }

    sumMap := map[string]int{}
    for name, cnt := range countMap {
        // 所有关系完成后再按最终代表聚合频次。
        root := uf.find(name)
        sumMap[root] += cnt
    }

    res := make([]string, 0, len(sumMap))
    for name, cnt := range sumMap {
        if cnt == 0 {
            continue
        }
        res = append(res, fmt.Sprintf("%s(%d)", name, cnt))
    }

    return res
}

type unionFind struct {
    parent map[string]string
}

func newUnionFind() *unionFind {
    return &unionFind{parent: make(map[string]string)}
}

func (u *unionFind) find(x string) string {
    if p, ok := u.parent[x]; ok {
        if p != x {
            u.parent[x] = u.find(p)
        }
        return u.parent[x]
    }
    // 同义关系中独有的名字也要登记，才能参与连通与代表选择。
    u.parent[x] = x
    return x
}

func (u *unionFind) union(a, b string) {
    pa := u.find(a)
    pb := u.find(b)
    if pa == pb {
        return
    }

    // 连接两个代表根，字典序较小者成为新代表。
    if pa < pb {
        u.parent[pb] = pa
    } else {
        u.parent[pa] = pb
    }
}

复杂度分析

时间复杂度：设 C 为输入字符串总长度，K 为不同名字数，L 为最长名字长度，F 为各次查找累计经过的父链接数。考虑字符串哈希与比较，期望上界为 $O(C+(F+K)L)$。代码按字典序连接而非按秩合并，不能直接套用“按秩合并加路径压缩”的反阿克曼界。

空间复杂度：$O(C+K)$，用于解析记录、父映射、频次汇总及结果。Java 查找只占常数临时空间；Go 单次递归查找的栈深度最坏为 $O(K)$，仍被整体空间上界包含。

关键点总结

[!green]

同义关系形成等价类，并查集自然处理间接同义。

让较大的根连接较小的根，归纳保证每组根始终是最小名字。

全部合并后再按最终根求和，避免依赖中途可能变化的代表。

易错点总结

[!yellow]

只登记频次表中的名字，会丢掉关系中的连接节点或更小代表。

合并时直接修改任意成员的父链接，可能只搬走集合的一部分，必须连接两个根。

把中间根直接当作最终分组，会把后来合并到一起的频次分开。

按字典序连接仍可能形成长链，路径压缩不能保证第一次递归查找的栈深度很小。

相似题目

题目	难度	关联与区别
721. 账户合并	中等	同义关系具有传递性，可像共享邮箱一样合并连通分量，再累计各组频次。
1061. 按字典序排列最小的等效字符串	中等	同样为等价类选字典序最小代表，本题代表名字可以来自只有同义关系而没有频次的条目。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/89929055

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！