需要教语言的最少人数
难度:
标签:
题目描述
代码结果
运行时间: 90 ms, 内存: 29.8 MB
/*
* 思路:
* 1. 使用Java Stream API进行集合操作。
* 2. 找出所有没有共同语言的好友对。
* 3. 对每一个语言,计算需要学习该语言的最少用户数。
* 4. 返回最小的需要学习用户数。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
Set<Integer> noCommonLangFriends = Arrays.stream(friendships)
.filter(f -> !hasCommonLanguage(languages[f[0] - 1], languages[f[1] - 1]))
.flatMapToInt(f -> IntStream.of(f[0] - 1, f[1] - 1))
.boxed()
.collect(Collectors.toSet());
return IntStream.rangeClosed(1, n)
.map(lang -> (int) noCommonLangFriends.stream()
.filter(user -> !containsLanguage(languages[user], lang))
.count())
.min()
.orElse(0);
}
private boolean hasCommonLanguage(int[] userLangs1, int[] userLangs2) {
Set<Integer> set = Arrays.stream(userLangs1).boxed().collect(Collectors.toSet());
return Arrays.stream(userLangs2).anyMatch(set::contains);
}
private boolean containsLanguage(int[] userLangs, int lang) {
return Arrays.stream(userLangs).anyMatch(l -> l == lang);
}
}
解释
方法:
这个题解采用的是贪心的策略。首先,将每个用户会的语言转换成集合,以便快速判断两个用户是否有共同语言。接着,遍历所有的好友关系,对于没有共同语言的好友对,统计他们各自的出现次数。然后,统计这些用户会的语言的出现次数。最后,找出这些用户会的语言中出现次数最多的那个,教给不会这门语言的用户,使得所有好友之间都可以相互沟通。需要教的人数就是不会这门语言的用户数减去已经会这门语言的用户数。
时间复杂度:
O(m*n + f*n)
空间复杂度:
O(m*n + m + n)
代码细节讲解
🦆
在这个题解中,你是如何保证在所有用户中选择一门语言来教授能满足最少教授人数的目标?
▷🦆
在实现函数`has_common`时,为什么选择使用循环遍历而不是使用集合的交集操作来判断两个用户是否有共同语言?
▷🦆
为什么在最后计算最少教授人数时,使用`len(p_cnt) - cnt`的方式来得出结果?这种计算方式的前提条件是什么?
▷