题目描述
思路解析
一句话答案：LeetCode 1733 需要教语言的最少人数：先把说不上话的好友两端收进集合 S，再枚举每门语言、选 S 里已会人数最多的那门统一教，答案 = |S| 减去它，时间 O(m·k²)。
只教一门语言，最少教几个人能让好友都聊上话
有 n 门语言，languages[i] 是第 i 位用户会的语言集合，friendships 列出若干对好友。一对好友能沟通，指两人至少有一门共同语言。你只能挑定一门语言，教给任意几个人，让每一对好友都能沟通，问最少教几个。好友关系没有传递性，x、y 是好友、y、z 是好友，不代表 x、z 是好友。题面第一个例子 n=2、languages=[[1],[2],[1,2]]，答案是 1。
五对好友里，真正卡住的是哪几对
好友只要已有共同语言，就不用碰。真正的麻烦只出在交集为空、也就是两人没有一门语言重合的那种好友对上。把这类说不上话的好友，两端一起收进集合 S。当前就能沟通的人不在 S 里，教他们任何语言都是白教，最少人数只会出在 S 这批人身上。
为什么全教同一门语言、还专挑已会人数最多的
题目卡死只能选一门语言 L，对 S 里的人只能统一教这一门。把 L 教给 S 中还不会 L 的人后，每条问题好友边——即前面收进集合 S 的那些说不上话的好友——的两端就都会 L，这对好友被修好。要教的人数，等于 S 的总人数减去 S 里本来就会 L 的人数——|S| 固定，要让差最小，就得让已会 L 的人数尽量大。于是枚举每门语言，数它在 S 里已有几人会，选已会最多那门，减完剩下就是最少要教的人。
三步写成代码，返回值到底减掉了谁
第一步用 check 判断两个用户有没有共同语言，参考代码里是最直白的双重循环，拿 u 的每门语言去和 v 的每门语言逐个比，相等返回真；遍历每对好友，check 为假就把 u、v 放进 S。第二步用计数器 cnt 走一遍 S 里的人，每人会的语言各记一票。第三步返回 len(S) 减去 cnt 的最高票，即 S 人数减去已会最多那门的人数。S 为空时没有票，返回 0。
n=2 的三人例子，S 和答案怎么落出来
拿题面第一个例子走一遍：用户1 会 {1}，用户2 会 {2}，用户3 会 {1,2}，好友有 (1,2)、(1,3)、(2,3)。(1,2)：{1} 和 {2} 没有重合，两人进 S，S={用户1, 用户2}。(1,3)：{1} 和 {1,2} 共有语言1，能沟通，跳过。(2,3)：{2} 和 {1,2} 共有语言2，跳过。三对看完，S={用户1, 用户2}。
再数 S 里的语言：用户1 会语言1，用户2 会语言2，两门各 1 人会，最高票 1。答案 = |S| 减最高票 = 2 − 1 = 1，教这 1 个人即可：给他补上另一人已会的那门，两人就有了共同语言。
这几处最容易写偏，复杂度也一并算清
想给不同的人教不同语言凑得更省，最招人上当，可题目只准选一门 L，唯有统一教 L，两端才同时会 L。把不在 S 的人也拉进来数，实则稀释每门语言的票数，最优语言和最少人数一起算歪。已会 L 的人天生就能用 L 沟通、不用教，若也算进要教的名单，就成了教满整个 S，正解是减去这批人。复杂度上，设好友对数为 m、单人语言数上限为 k：建 S 时逐对双重循环判交集，是 O(m·k²)；之后只在 S 内统计一遍，是 O(|S|·k)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
三步走:交集为空的好友两端进问题集 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题