leetcode
leetcode 1551 ~ 1600
需要教语言的最少人数

需要教语言的最少人数

难度:

标签:

题目描述

代码结果

运行时间: 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`时,为什么选择使用循环遍历而不是使用集合的交集操作来判断两个用户是否有共同语言?
在实现`has_common`函数时,选择使用循环遍历的原因可能是出于效率的考虑。虽然使用集合的交集操作(如`set1 & set2`)可以直接判断两个集合是否有共同元素,但这种方法会产生一个新的集合,可能涉及额外的内存分配和计算开销。相反,循环遍历列表并检查元素是否存在于另一个集合中(使用`in`操作符),可以在找到第一个共同元素时立即停止,这样在最佳情况下可以更快地返回结果,尤其是当共同语言出现在列表的开始部分时。
🦆
为什么在最后计算最少教授人数时,使用`len(p_cnt) - cnt`的方式来得出结果?这种计算方式的前提条件是什么?
在最后计算最少教授人数时,使用`len(p_cnt) - cnt`的方式基于以下前提条件:`p_cnt`记录的是所有需要通过教授新语言来实现沟通的用户数量(即没有共同语言的好友对中的用户),而`cnt`是这些用户中已经会某一特定语言(出现次数最多的语言)的用户数量。这样,`len(p_cnt) - cnt`实际上计算的是在已经确定最优语言之后,还需要被教授这门语言的用户数量。这种计算方式假设最优语言是能够最大程度减少教授需求的语言,即这种语言已经被尽可能多的目标用户掌握。

相关问题