需要教语言的最少人数 图解题解
这道题到底在问什么
- 输入
- n=2, langs=[[1],[2],[1,2]], fr=[[1,2],[1,3],[2,3]]
- 输出
- 1
- 输入
- n=1, langs=[[1],[1]], fr=[[1,2]]
- 输出
- 0
- 输入
- n=3, langs=[[1],[2],[3]], fr=[[1,2],[2,3]]
- 输出
- 2
先想最直接的笨办法
第二步开始统计。我们准备三个计数器,分别记语言1、语言2、语言3 在问题集 S 里已经有几个人会,现在都是 0。为什么只数 S 里的人?因为不在 S 的人本来就没沟通问题,教他们纯属浪费。挨个看 S 里的用户,把他会的语言计数加一。（动画第 17 步）
最优解：一步一步想明白
- 3三步走:交集为空的好友两端进问题集 S;只在 S 内数每门语言的人数;答案 = |S| 减去已会人数最多那门语言的人数。
- 4先看清画面。上面这排是 5 位用户,右边表里写着每人会的语言:用户1只会语言1,用户2只会语言2,用户3会语言1和2,用户4会语言1,用户5会语言3。两个好友要能聊天,必须有共同语言。我们的任务是挑一门语言去教,让所有好友都能沟通,而且教的人越少越好。
- 5第一步,把说不上话的好友挑出来。一共有五对好友:(1,2)、(1,3)、(2,3)、(2,4)、(1,5)。我们一对一对地看两人的语言集合有没有交集。有交集的就跳过,没交集的说明他们现在聊不了,就把这两个人一起放进「问题集 S」。现在 S 还是空的,从第一对开始。
- 6看好友对 (1,2)。用户1 会 {1},用户2 会 {2}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 还是空的。
- 7交集是 ∅,空的。用户1 和用户2 没有任何共同语言,现在根本聊不了,所以两个人一起加入问题集 S,在数组上标成红色。加完之后 S = {用户1, 用户2}。
- 8看好友对 (1,3)。用户1 会 {1},用户3 会 {1,2}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2}(红色标出)。
- 9交集是 {1},不空。用户1 和用户3 靠语言1 就能沟通(绿色标出),这对好友没问题,直接跳过,S 保持 {用户1, 用户2} 不变。
- 10看好友对 (2,3)。用户2 会 {2},用户3 会 {1,2}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2}(红色标出)。
- 11交集是 {2},不空。用户2 和用户3 靠语言2 就能沟通(绿色标出),这对好友没问题,直接跳过,S 保持 {用户1, 用户2} 不变。
- 12看好友对 (2,4)。用户2 会 {2},用户4 会 {1}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2}(红色标出)。
- 13交集是 ∅,空的。用户2 和用户4 没有任何共同语言,现在根本聊不了,所以两个人一起加入问题集 S,在数组上标成红色。加完之后 S = {用户1, 用户2, 用户4}。
- 14看好友对 (1,5)。用户1 会 {1},用户5 会 {3}。把两个集合放一起,看看它们有没有共同的语言。此刻问题集 S 里已经有 {用户1, 用户2, 用户4}(红色标出)。
- 15交集是 ∅,空的。用户1 和用户5 没有任何共同语言,现在根本聊不了,所以两个人一起加入问题集 S,在数组上标成红色。加完之后 S = {用户1, 用户2, 用户4, 用户5}。
- 16五对好友全看完了。红色的用户1、用户2、用户4、用户5 都出现在某对说不上话的好友里,进了问题集 S,一共 4 人。用户3 一直没进 S,因为它和好友1、好友2 都能靠语言沟通,压根不用教。接下来只盯着 S 这 4 个人,数一数每门语言已经有多少人会。
- 17第二步开始统计。我们准备三个计数器,分别记语言1、语言2、语言3 在问题集 S 里已经有几个人会,现在都是 0。为什么只数 S 里的人?因为不在 S 的人本来就没沟通问题,教他们纯属浪费。挨个看 S 里的用户,把他会的语言计数加一。
- 18轮到用户1(紫色),它会 {1}。把语言1 的计数从 0 加到 1。这门语言暂时领先,当前最多有 1 人会。
- 19轮到用户2(紫色),它会 {2}。把语言2 的计数从 0 加到 1。语言2 追平语言1,当前最多仍是 1 人会。
- 20轮到用户4(紫色),它会 {1}。把语言1 的计数从 1 加到 2。这门语言暂时领先,当前最多有 2 人会。
- 21轮到用户5(紫色),它会 {3}。把语言3 的计数从 0 加到 1。当前领先的语言已会 2 人。
- 22统计完了:语言1 在 S 里有 2 人会(用户1、用户4,标绿),语言2 有 1 人会,语言3 有 1 人会。语言1 已会的人最多,所以就选它作为要教的那一门。已经会语言1 的用户1、用户4 不用教;还不会语言1 的用户2、用户5 标成红色,正是要教的对象。
- 23算总账。S 里 4 个人,其中 2 个已经会语言1,那么只要把语言1 教给剩下还不会的用户2 和用户5 就够了。答案 = S 的人数 4 减去已会语言1 的 2 人,等于 2。教完之后,S 里 4 个人全都会语言1,那三对原本说不上话的好友(两端都在 S 里)就都能沟通了。
- 24回顾整条链:先逐对好友挑出说不上话的两端,凑成问题集 S = {用户1,2,4,5};再只在 S 里数语言人数,语言1 已会的人最多有 2 个;最后把语言1 教给还不会的 2 个人。全绿表示 S 里 4 人现在都会语言1,所有好友都能沟通。最少要教 2 名用户。窍门就一句:交集为空的好友进 S,教 S 里已会人数最多的那门语言。
⚠️ 容易写错的地方
✗ 错：想给不同的人教不同语言,以为这样更省
✓ 对：全程只能选一门语言 L,教给问题集里所有还不会 L 的人
本题硬性规定只能选定一门语言 L,所以必须统一选 L。统一教 L 后,S 里还不会 L 的人被补齐,问题好友的两个端点都会 L,因此这些边都被修复
✗ 错：把所有人都拿去数语言,或者把不在好友里的人也算进来
✓ 对：只把出现在「说不上话」好友对里的人放进 S,只在 S 内统计
当前所有好友都能沟通的人,不需要任何改动,教他们是浪费。把他们算进统计会稀释语言计数,选出的最优语言和最少人数都会算错。范围必须严格锁在 S
✗ 错：误以为 S 里已经会最多语言那门的人也要教
✓ 对：答案 = |S| 减去 S 内已会该语言的人数,已会的人省下不教
选中语言 L 后,S 里已经会 L 的人天生就能和别人用 L 沟通,一个都不用教。真正要教的只是 S 里还不会 L 的那部分,所以是「减去已会人数」而不是直接教全部 S
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
unordered_set<int> s;
auto check = [&](int u, int v) {
for (int x : languages[u - 1]) {
for (int y : languages[v - 1]) {
if (x == y) {
return true;
}
}
}
return false;
};
for (auto& e : friendships) {
int u = e[0], v = e[1];
if (!check(u, v)) {
s.insert(u);
s.insert(v);
}
}
if (s.empty()) {
return 0;
}
vector<int> cnt(n + 1);
for (int u : s) {
for (int& l : languages[u - 1]) {
++cnt[l];
}
}
return s.size() - *max_element(cnt.begin(), cnt.end());
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
Set<Integer> s = new HashSet<>();
for (int[] e : friendships) {
int u = e[0], v = e[1];
if (!check(u, v, languages)) {
s.add(u);
s.add(v);
}
}
if (s.isEmpty()) {
return 0;
}
int[] cnt = new int[n + 1];
for (int u : s) {
for (int l : languages[u - 1]) {
++cnt[l];
}
}
int mx = 0;
for (int v : cnt) {
mx = Math.max(mx, v);
}
return s.size() - mx;
}
private boolean check(int u, int v, int[][] languages) {
for (int x : languages[u - 1]) {
for (int y : languages[v - 1]) {
if (x == y) {
return true;
}
}
}
return false;
}
}复杂度
时间
O(m·k² + |S|·k)
设好友数为 m、单个用户会的语言数上限为 k。第一步对每条好友关系判断有没有共同语言,参考代码用双重循环两两比对,是语言数的平方级 O(k²),所以建问题集是 O(m·k²);第二步只遍历 S 里的人累加语言计数,是 O(|S|·k)。若把每个人的语言先放进哈希集合判交集,第一步可降到 O(m·k)
空间
O(用户数 + 语言数)
按峰值算。问题集 S 最多装下所有出现在好友里的用户,是 O(用户数);语言计数无论用定长数组还是哈希表,都是 O(语言数 n)。两者相加,没有更大的额外结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 需要教语言的最少人数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么只教一门语言就够,教多门会不会更优?+
本题硬性规定只能选定一门语言来教,这是硬约束。所以我们必须枚举这一门语言,在这门语言的候选里最小化 |S| 减去 S 里已经会这门语言的人数,取最小值就是答案。要强调的是,这个贪心只在「只能选一门」的前提下成立。如果题意改成允许给不同的人教不同语言(仍然按被教的人计数),那就是另一个问题了,本题的贪心不能直接套用,答案甚至可能更省人。所以别把「只教一门」当成普遍最优,它只是本题硬约束下的最优解法。
为什么不用把不在任何问题好友里的人考虑进来?+
因为那些人当前所有好友都已经能沟通,他们身上没有任何需要修复的连接。教他们任何语言都不会减少要教的总数,反而是白教。所以我们只把出现在「说不上话」好友对里的人收进问题集 S,统计和结算都只在 S 内进行。把无关的人算进来,只会稀释语言计数、把最优语言和最少人数都算歪。
判断两个人有没有共同语言,除了双重循环还有更快的写法吗?+
有。参考代码用的是最直观的双重循环,拿一个人的每门语言去和另一个人的每门语言逐个比,是语言数的平方级。更快的做法是先把每个人会的语言放进一个哈希集合,判断另一个人是否有语言落在这个集合里,单次查询接近常数,整体从平方级降到线性。当每个人会的语言不多时,两种写法差别不明显;语言数一大,哈希集合的优势就体现出来了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 需要教语言的最少人数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。