题目描述
在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：
- 总共有
n 种语言，编号从 1 到 n 。
languages[i] 是第 i 位用户掌握的语言集合。friendships[i] = [ui, vi] 表示 ui 和 vi 为好友关系。
你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。
示例 1：
输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出：1
解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。
示例 2：
输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2
解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。
提示：
2 <= n <= 500languages.length == m1 <= m <= 5001 <= languages[i].length <= n1 <= languages[i][j] <= n1 <= ui < vi <= languages.length1 <= friendships.length <= 500- 所有的好友关系
(ui, vi) 都是唯一的。
languages[i] 中包含的值互不相同。
解法
方法一：模拟 + 统计
对于每个好友关系，如果两个人掌握的语言集合不相交，则需要教一门语言，使得两个人可以相互沟通，我们将这些人放入一个哈希集合 \(s\) 中。
然后在这个集合 \(s\) 中，统计每种语言掌握的人数，获取最大的人数，我们记为 \(mx\)，那么答案就是 \(|s| - mx\)。其中 \(|s|\) 表示集合 \(s\) 的大小。
时间复杂度 \(O(m^2 \times k)\)。其中 \(m\) 为语言的数量，而 \(k\) 为好友关系的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
Set<Integer> s = new HashSet<>();
for (var 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | 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() - ranges::max(cnt);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
check := func(u, v int) bool {
for _, x := range languages[u-1] {
for _, y := range languages[v-1] {
if x == y {
return true
}
}
}
return false
}
s := map[int]bool{}
for _, e := range friendships {
u, v := e[0], e[1]
if !check(u, v) {
s[u], s[v] = true, true
}
}
if len(s) == 0 {
return 0
}
cnt := make([]int, n+1)
for u := range s {
for _, l := range languages[u-1] {
cnt[l]++
}
}
return len(s) - slices.Max(cnt)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | function minimumTeachings(n: number, languages: number[][], friendships: number[][]): number {
function check(u: number, v: number): boolean {
for (const x of languages[u - 1]) {
for (const y of languages[v - 1]) {
if (x === y) {
return true;
}
}
}
return false;
}
const s = new Set<number>();
for (const [u, v] of friendships) {
if (!check(u, v)) {
s.add(u);
s.add(v);
}
}
const cnt = new Map<number, number>();
for (const u of s) {
for (const l of languages[u - 1]) {
cnt.set(l, (cnt.get(l) || 0) + 1);
}
}
return s.size - Math.max(0, ...cnt.values());
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | use std::collections::{HashSet, HashMap};
impl Solution {
pub fn minimum_teachings(n: i32, languages: Vec<Vec<i32>>, friendships: Vec<Vec<i32>>) -> i32 {
fn check(u: usize, v: usize, languages: &Vec<Vec<i32>>) -> bool {
for &x in &languages[u - 1] {
for &y in &languages[v - 1] {
if x == y {
return true;
}
}
}
false
}
let mut s: HashSet<usize> = HashSet::new();
for edge in friendships.iter() {
let u = edge[0] as usize;
let v = edge[1] as usize;
if !check(u, v, &languages) {
s.insert(u);
s.insert(v);
}
}
let mut cnt: HashMap<i32, i32> = HashMap::new();
for &u in s.iter() {
for &l in &languages[u - 1] {
*cnt.entry(l).or_insert(0) += 1;
}
}
let mx = cnt.values().cloned().max().unwrap_or(0);
(s.len() as i32) - mx
}
}
|