题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
- 每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。
- 有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。
- 给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。
- 设计一个算法打印出每个真实名字的实际频率。
- 注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
- 在结果列表中，选择字典序最小的名字作为真实名字。
- names.length <= 100000
题目样例
示例
输入
names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出
["John(27)","Chris(36)"]
题目思考
- 如何得到每个名字的真实名字?
- 需要额外记录什么信息?
解决方案
思路
- 分析题目, 我们需要根据提供的名字对信息, 得到所有具有相同真实名字的名字集合, 然后累计其频率并输出
- 这里我们可以利用经典的并查集算法, 就是将元素进行分类, 相同的放在同一个集合中
- 当然靠暴力模拟也可以做到归类, 但是那样会涉及到耗时巨大的集合求并集和循环判断等, 效率过低; 而并查集可以做到每次操作只需要 O(logN)甚至更短的时间
- 并查集的思路很简单, 具体步骤如下:
- 首先我们需要定义一个字典 pre, pre[x]表示 x 的祖先, 如果两个元素具有相同祖先, 就表示它们在同一个集合中. 可以把祖先 pre[x] 想象成一个树的根节点, 那么 x 就是树中的一个节点(可能是根节点本身)
- 然后定义一个 find 方法, 查找当前元素的祖先, 如果祖先不存在的话就把自身当做祖先. 这里用到了路径压缩的优化, 就是说当发现自己的祖先不是自身的时候, 就尝试把自己的祖先设置为自己的当前祖先的祖先, 从而降低树的高度, 加快之后的查找过程
- 最后定义一个 union 方法, 用于合并两个元素. 这里的思路也很简单, 就是找到各自的祖先, 然后将其中一个的祖先的祖先设置为另外一个祖先即可, 等于就把两个树合并在了一起
- 注意这道题相比传统并查集多了两个条件, 一是要求祖先最小, 二是需要求频率之和
- 针对第一个需求, 我们可以更改 union 方法, 将字典序较大的祖先指向字典序较小的祖先, 这样就能保证最终的祖先一定是字典序最小的
- 针对第二个需求, 我们可以额外引入一个计数字典, 记录祖先的频率, 每次遍历到一个新名字, 其对应的祖先的频率就加上当前的频率
- 然后最终再遍历计数字典, 将 kv 转换成结果的格式即可
- 下面的代码中对每个步骤都有注释, 方便大家理解
复杂度
- 时间复杂度 O((N+M)logN): 假设 N 为名字个数, M 为名字对个数, 那么需要分别循环 M 和 N 合并和统计频率, 每次 find/union 操作需要 logN 时间, 所以总共复杂度就是 O((N+M)logN)
- 空间复杂度 O(N): pre 字典中存 N 个名字
代码
class Solution:
def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
# 并查集变种, 先找到所有相同的名字, 然后再统计数字
# 注意祖先需要是字典序最小的, 所以需要稍微改动union逻辑
pre = {}
def find(x):
if x not in pre:
pre[x] = x
elif pre[x] != x:
pre[x] = find(pre[x])
return pre[x]
def union(x, y):
px = find(x)
py = find(y)
# 保证祖先的字典序更小
if px > py:
pre[px] = py
else:
pre[py] = px
for s in synonyms:
# parse两个名字, 并合并
x, y = s[1:-1].split(",")
union(x, y)
cnts = collections.defaultdict(int)
for t in names:
i = t.find("(")
# parse当前名字和频率
name = t[:i]
cnt = int(t[i + 1 : t.find(")")])
# 累加到祖先对应的频率中
cnts[find(name)] += cnt
res = []
for k in cnts:
# 转换成结果要求的格式
res.append(k + "(" + str(cnts[k]) + ")")
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号