题目描述
思路解析动画文字版
三步走:交集为空的好友两端进问题集 S;只在 S 内数每门语言的人数;答案 = |S| 减去已会人数最多那门语言的人数。
总览 · 5 位用户 + 各自语言：先看清画面。上面这排是 5 位用户,右边表里写着每人会的语言:用户1只会语言1,用户2只会语言2,用户3会语言1和2,用户4会语言1,用户5会语言3。两个好友要能聊天,必须有共同语言。我们的任务是挑一门语言去教,让所有好友都能沟通,而且教的人越少越好。
第一步 · 挑出说不上话的好友：第一步,把说不上话的好友挑出来。一共有五对好友:(1,2)、(1,3)、(2,3)、(2,4)、(1,5)。我们一对一对地看两人的语言集合有没有交集。有交集的就跳过,没交集的说明他们现在聊不了,就把这两个人一起放进「问题集 S」。现在 S 还是空的,从第一对开始。
检查 · 好友(1,2)：看好友对 (1,2)。用户1 会 {1},用户2 会 {2}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 还是空的。
判定 · 进 S：交集是 ∅,空的。用户1 和用户2 没有任何共同语言,现在根本聊不了,所以两个人一起加入问题集 S,在数组上标成红色。加完之后 S = {用户1, 用户2}。
检查 · 好友(1,3)：看好友对 (1,3)。用户1 会 {1},用户3 会 {1,2}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2}(红色标出)。
判定 · 跳过：交集是 {1},不空。用户1 和用户3 靠语言1 就能沟通(绿色标出),这对好友没问题,直接跳过,S 保持 {用户1, 用户2} 不变。
检查 · 好友(2,3)：看好友对 (2,3)。用户2 会 {2},用户3 会 {1,2}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2}(红色标出)。
判定 · 跳过：交集是 {2},不空。用户2 和用户3 靠语言2 就能沟通(绿色标出),这对好友没问题,直接跳过,S 保持 {用户1, 用户2} 不变。
检查 · 好友(2,4)：看好友对 (2,4)。用户2 会 {2},用户4 会 {1}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2}(红色标出)。
判定 · 进 S：交集是 ∅,空的。用户2 和用户4 没有任何共同语言,现在根本聊不了,所以两个人一起加入问题集 S,在数组上标成红色。加完之后 S = {用户1, 用户2, 用户4}。
检查 · 好友(1,5)：看好友对 (1,5)。用户1 会 {1},用户5 会 {3}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2, 用户4}(红色标出)。
判定 · 进 S：交集是 ∅,空的。用户1 和用户5 没有任何共同语言,现在根本聊不了,所以两个人一起加入问题集 S,在数组上标成红色。加完之后 S = {用户1, 用户2, 用户4, 用户5}。
问题集 S = {用户1,2,4,5}：五对好友全看完了。红色的用户1、用户2、用户4、用户5 都出现在某对说不上话的好友里,进了问题集 S,一共 4 人。用户3 一直没进 S,因为它和好友1、好友2 都能靠语言沟通,压根不用教。接下来只盯着 S 这 4 个人,数一数每门语言已经有多少人会。
第二步 · S 内语言计数：第二步开始统计。我们准备三个计数器,分别记语言1、语言2、语言3 在问题集 S 里已经有几个人会,现在都是 0。为什么只数 S 里的人?因为不在 S 的人本来就没沟通问题,教他们纯属浪费。挨个看 S 里的用户,把他会的语言计数加一。
统计 · 用户1 会语言1：轮到用户1(紫色),它会 {1}。把语言1 的计数从 0 加到 1。这门语言暂时领先,当前最多有 1 人会。
统计 · 用户2 会语言2：轮到用户2(紫色),它会 {2}。把语言2 的计数从 0 加到 1。语言2 追平语言1,当前最多仍是 1 人会。
统计 · 用户4 会语言1：轮到用户4(紫色),它会 {1}。把语言1 的计数从 1 加到 2。这门语言暂时领先,当前最多有 2 人会。
统计 · 用户5 会语言3：轮到用户5(紫色),它会 {3}。把语言3 的计数从 0 加到 1。当前领先的语言已会 2 人。
选最省 · 语言1(2 人已会)：统计完了:语言1 在 S 里有 2 人会(用户1、用户4,标绿),语言2 有 1 人会,语言3 有 1 人会。语言1 已会的人最多,所以就选它作为要教的那一门。已经会语言1 的用户1、用户4 不用教;还不会语言1 的用户2、用户5 标成红色,正是要教的对象。
结算 · 最少教 2 人：算总账。S 里 4 个人,其中 2 个已经会语言1,那么只要把语言1 教给剩下还不会的用户2 和用户5 就够了。答案 = S 的人数 4 减去已会语言1 的 2 人,等于 2。教完之后,S 里 4 个人全都会语言1,那三对原本说不上话的好友(两端都在 S 里)就都能沟通了。
完成 · 答案 = 2：回顾整条链:先逐对好友挑出说不上话的两端,凑成问题集 S = {用户1,2,4,5};再只在 S 里数语言人数,语言1 已会的人最多有 2 个;最后把语言1 教给还不会的 2 个人。全绿表示 S 里 4 人现在都会语言1,所有好友都能沟通。最少要教 2 名用户。窍门就一句:交集为空的好友进 S,教 S 里已会人数最多的那门语言。
边界:好友本就有共同语言时 S 为空、答案 0;S 里每门语言都只有 1 人会时答案 = |S| 减 1;全体同语言时一个都不用教。
面试重点:本题硬性规定只能选一门语言统一教,贪心正建立在这个硬约束上(题意若允许教多门则是另一个问题,不能直接套);只处理出现在问题好友里的人;判交集可用哈希集合把平方级降到线性。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def minimumTeachings( self, n: int, languages: List[List[int]], friendships: List[List[int]] ) -> int: def check(u: int, v: int) -> bool: for x in languages[u - 1]: for y in languages[v - 1]: if x == y: return True return False s = set() for u, v in friendships: if not check(u, v): s.add(u) s.add(v) cnt = Counter() for u in s: for l in languages[u - 1]: cnt[l] += 1 return len(s) - max(cnt.values(), default=0)复杂度
- 时间：O(m·k² + |S|·k)，设好友数为 m、单个用户会的语言数上限为 k。第一步对每条好友关系判断有没有共同语言,参考代码用双重循环两两比对,是语言数的平方级 O(k²),所以建问题集是 O(m·k²);第二步只遍历 S 里的人累加语言计数,是 O(|S|·k)。若把每个人的语言先放进哈希集合判交集,第一步可降到 O(m·k)
- 空间：O(用户数 + 语言数)，按峰值算。问题集 S 最多装下所有出现在好友里的用户,是 O(用户数);语言计数无论用定长数组还是哈希表,都是 O(语言数 n)。两者相加,没有更大的额外结构
易错点
面试追问把动画讲成自己的话
追问为什么只教一门语言就够,教多门会不会更优?
追问为什么不用把不在任何问题好友里的人考虑进来?
追问判断两个人有没有共同语言,除了双重循环还有更快的写法吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
你能构造出连续值的最大数目
LeetCode 1798 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题