婴儿名字

难度: Medium

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择 字典序最小 的名字作为真实名字。

示例：

输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]

提示：

names.length <= 100000

Submission

运行时间: 132 ms

内存: 19.5 MB

class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        if len(names) <= 0:
            return []
        
        # union find set
        syn_map = dict()
        for x in synonyms:
            child, parent = x.split(',')
            child = child.lstrip('(')
            parent = parent.rstrip(')')
            root1 = child
            while root1 in syn_map:
                root1 = syn_map[root1]
            root2 = parent
            while root2 in syn_map:
                root2 = syn_map[root2]
            if root1 == root2:
                continue    
                
            if root1 < root2:
                syn_map[root2] = root1
            else:
                syn_map[root1] = root2
                
        #print(synonyms)
        #print(syn_map)
        #exit(0)
            
        freq_map = dict()
        for x in names:
            name, freq = x.split('(')
            freq = int(freq.split(')')[0])
            root = name
            while root in syn_map:
                root = syn_map[root]
            freq_map[root] = freq_map.get(root, 0) + freq
            
        return ["{}({})".format(k, v) for k, v in freq_map.items()]

Explain

此题解采用了并查集的数据结构来处理名字的等价关系。首先，通过处理synonyms列表来构建一个等价关系图，将具有相同含义的名字进行合并。合并规则是，总是让字典序较小的名字作为代表。接着，通过遍历names列表，将每个名字的频率累加到其根节点（即代表名字）上。最后，输出所有有频率记录的根节点及其对应的频率。这种方法有效地将所有同义名字归并到一个名字上，并且处理了名字间的传递性等价关系。

时间复杂度: O((A + B) * α(N))

空间复杂度: O(N)

class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        if len(names) <= 0:
            return []
        
        # 使用并查集来处理名字的等价关系
        syn_map = dict()
        for x in synonyms:
            child, parent = x.split(',')
            child = child.lstrip('(')
            parent = parent.rstrip(')')
            # 查找每个名字当前的根节点
            root1 = child
            while root1 in syn_map:
                root1 = syn_map[root1]
            root2 = parent
            while root2 in syn_map:
                root2 = syn_map[root2]
            # 如果根节点相同，说明已在同一集合中
            if root1 == root2:
                continue
            
            # 将根节点字典序较大的名字合并到字典序较小的名字下
            if root1 < root2:
                syn_map[root2] = root1
            else:
                syn_map[root1] = root2
                
        # 统计每个根节点的频率
        freq_map = dict()
        for x in names:
            name, freq = x.split('(')
            freq = int(freq.split(')')[0])
            root = name
            while root in syn_map:
                root = syn_map[root]
            freq_map[root] = freq_map.get(root, 0) + freq
            
        # 输出格式化的结果
        return ["{}({})".format(k, v) for k, v in freq_map.items()]

Explore

在并查集的实现中，每次合并两个集合时，会先找到两个名字的根节点。接着，比较这两个根节点的字典序，将字典序较大的名字的根节点指向字典序较小的名字的根节点。这样，每个集合的代表（根节点）总是字典序最小的名字。具体逻辑是：1) 通过递归或迭代找到每个名字的根节点；2) 比较两个根节点的字典序；3) 更新较大字典序名字的根节点指针，指向较小字典序名字的根节点。这种做法确保了合并后的根节点总是最小字典序的名字，保持了集合的有序性。

在并查集中，为了优化长链条问题，可以使用两种主要的技术：路径压缩和按秩合并。路径压缩是在查找根节点的过程中，将查找路径上的每个节点直接连接到根节点，从而减少后续查找时间。按秩合并是根据每个节点的秩（通常是树的高度或大小）来决定合并方向，一般将秩较小的根节点指向秩较大的根节点，这样可以避免树过度增长。通过这两种技术，可以显著减少查找根节点的平均时间复杂度，使得并查集操作更加高效。

在处理名字频率时，首先将每个名字的频率加到其对应的根节点上。具体操作是：1) 对于每个名字，通过并查集找到其根节点；2) 将名字的频率累加到根节点的频率上。这样，即使多个名字因为同义关系合并到一起，它们的频率也会被正确地加到同一个根节点上。最终，频率映射表中只记录每个根节点的总频率，而非合并前的各个名字的频率。这样可以确保输出的是合并后的名字及其总频率。