企业官网建设流程全解析

题目

标题和出处

标题：需要教语言的最少人数

出处：1733. 需要教语言的最少人数

难度

5 级

题目描述

要求

在一个由m \texttt{m}m个用户组成的社交网络中，有一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。

给定整数n \texttt{n}n、数组languages \texttt{languages}languages和数组friendships \texttt{friendships}friendships，它们的含义如下：

• 总共有n \texttt{n}n种语言，编号从1 \texttt{1}1到n \texttt{n}n。
• languages[i] \texttt{languages[i]}languages[i]是第i \texttt{i}i名用户掌握的语言集合。
• friendships[i] = [u i ​​​ , v i ] \texttt{friendships[i] = [u}_\texttt{i}​​​\texttt{, v}_\texttt{i}\texttt{]}friendships[i] = [ui​​​​, vi​]表示u i \texttt{u}_\texttt{i}ui​和v i \texttt{v}_\texttt{i}vi​为好友关系。

可以选择一门语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回最少需要教会多少名用户。

请注意，好友关系没有传递性，如果x \texttt{x}x和y \texttt{y}y是好友且y \texttt{y}y和z \texttt{z}z是好友，x \texttt{x}x和z \texttt{z}z不一定是好友。

示例

示例 1：

输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]] \texttt{n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]}n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出：1 \texttt{1}1
解释：可以选择教用户1 \texttt{1}1第二门语言，或选择教用户2 \texttt{2}2第一门语言。

示例 2：

输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]] \texttt{n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]}n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2 \texttt{2}2
解释：教用户1 \texttt{1}1和用户3 \texttt{3}3第三门语言，需要教2 \texttt{2}2名用户。

数据范围

• 2 ≤ n ≤ 500 \texttt{2} \le \texttt{n} \le \texttt{500}2≤n≤500
• languages.length = m \texttt{languages.length} = \texttt{m}languages.length=m
• 1 ≤ m ≤ 500 \texttt{1} \le \texttt{m} \le \texttt{500}1≤m≤500
• 1 ≤ languages[i].length ≤ n \texttt{1} \le \texttt{languages[i].length} \le \texttt{n}1≤languages[i].length≤n
• 1 ≤ languages[i][j] ≤ n \texttt{1} \le \texttt{languages[i][j]} \le \texttt{n}1≤languages[i][j]≤n
• 1 ≤ u i < v i ≤ m \texttt{1} \le \texttt{u}_\texttt{i} < \texttt{v}_\texttt{i} \le \texttt{m}1≤ui​<vi​≤m
• 1 ≤ friendships.length ≤ 500 \texttt{1} \le \texttt{friendships.length} \le \texttt{500}1≤friendships.length≤500
• 所有的好友关系(u i , v i ) \texttt{(u}_\texttt{i}\texttt{, v}_\texttt{i}\texttt{)}(ui​, vi​)各不相同
• languages[i] \texttt{languages[i]}languages[i]中包含的值各不相同

解法

思路和算法

为了使教语言的人数最少，应遵循如下贪心策略。

1. 只有当一对好友没有共同掌握的语言时，才需要教其中至少一个用户一种语言。

2. 对于上述用户，应选择这些用户中的掌握人数最多的语言，把该语言教给未掌握该语言的用户，则可满足上述用户都能掌握同一门语言且教语言的人数最少。

如果减少教语言的人数，则一定不能使上述用户都掌握同一种语言，也不能使所有的好友之间可以沟通，因此使用贪心策略可以得到需要教语言的最少人数。

具体做法如下。

1. 遍历数组languages \textit{languages}languages记录每个用户掌握的所有语言。

2. 遍历数组friendships \textit{friendships}friendships判断每一对好友是否有共同掌握的语言，使用哈希集合存储存在好友没有共同掌握的语言的用户。如果一对好友没有共同掌握的语言，则将这对好友的两个用户都加入哈希集合。

3. 对于每种语言统计哈希集合中的未掌握该语言的人数，其中的最少人数即为需要教语言的最少人数。

实现方面，由于数组languages \textit{languages}languages中的语言编号和数组friendships \textit{friendships}friendships中的用户编号都是从1 11开始的编号，为了方便处理，需要将语言编号和用户编号都转换成从0 00开始的编号。

代码

classSolution{publicintminimumTeachings(intn,int[][]languages,int[][]friendships){intm=languages.length;boolean[][]usersLanguages=newboolean[m][n];for(inti=0;i<m;i++){for(intj:languages[i]){usersLanguages[i][j-1]=true;}}Set<Integer>uncommon=newHashSet<Integer>();for(int[]friendship:friendships){intu=friendship[0]-1,v=friendship[1]-1;booleanhasCommon=false;for(intj=0;j<n&&!hasCommon;j++){if(usersLanguages[u][j]&&usersLanguages[v][j]){hasCommon=true;}}if(!hasCommon){uncommon.add(u);uncommon.add(v);}}int[]counts=newint[n];for(inti:uncommon){for(intj=0;j<n;j++){if(!usersLanguages[i][j]){counts[j]++;}}}returnArrays.stream(counts).min().getAsInt();}}

复杂度分析

• 时间复杂度：O ( m n + p n ) O(mn + pn)O(mn+pn)，其中m mm是用户的数量，n nn是语言的数量，p pp是好友关系的数量。遍历数组languages \textit{languages}languages记录每个用户掌握的所有语言的时间是O ( m n ) O(mn)O(mn)，遍历数组friendships \textit{friendships}friendships判断每一对好友是否有共同掌握的语言并使用哈希集合存储用户的时间是O ( p n ) O(pn)O(pn)，对于每种语言统计哈希集合中的未掌握该语言的人数的时间是O ( m n ) O(mn)O(mn)，因此时间复杂度是O ( m n + p n ) O(mn + pn)O(mn+pn)。

• 空间复杂度：O ( m n ) O(mn)O(mn)，其中m mm是用户的数量，n nn是语言的数量。记录每个用户掌握的所有语言的空间是O ( m n ) O(mn)O(mn)，哈希集合的空间是O ( m ) O(m)O(m)，统计每种语言的未掌握人数的空间是O ( n ) O(n)O(n)，因此空间复杂度是O ( m n ) O(mn)O(mn)。