需要教语言的最少人数

难度: Medium

在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。

给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：

总共有 n 种语言，编号从 1 到 n 。
languages[i] 是第 i 位用户掌握的语言集合。
friendships[i] = [u_i, v_i] 表示 u_i 和 v_i 为好友关系。

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

请注意，好友关系没有传递性，也就是说如果 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 <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
所有的好友关系 (u_i,v_i) 都是唯一的。
languages[i] 中包含的值互不相同。

Submission

运行时间: 90 ms

内存: 29.8 MB

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        # 没想到，居然是... 只是统计计数就可以...!!!!!
        # 贪心：统计所有的无法沟通的好友们，找到他们会的最多的语言，教给所有这些人中不会这门语言的人.
        # 但是每对人两两就需要确定出来共同语言... 会很慢的吧???
        # 我日，只能这么暴力...
        
        tmp = [None] * len(languages)   # set 化，大幅降低复杂度!!!
        for i, langs in enumerate(languages):
            tmp[i] = set(langs)
        
        def has_common(p1, p2):
            for lang1 in tmp[p1-1]:
                if lang1 in tmp[p2-1]:
                    return True
            return False
        
        p_cnt = Counter()
        # 统计没有共同语言的总人数
        for p1, p2 in friendships:
            if not has_common(p1, p2):
                p_cnt[p1] += 1
                p_cnt[p2] += 1
        
        if len(p_cnt) == 0:
            # 所有人都可正常交流...
            return 0
        
        lang_cnt = Counter()
        # 统计这些人会的语言总数
        for p, _ in p_cnt.items():
            for lang in languages[p - 1]:
                lang_cnt[lang] += 1
        
        best_lang, cnt = lang_cnt.most_common(1)[0]  # 会的最多的语言
        return len(p_cnt) - cnt

Explain

这个题解采用的是贪心的策略。首先，将每个用户会的语言转换成集合，以便快速判断两个用户是否有共同语言。接着，遍历所有的好友关系，对于没有共同语言的好友对，统计他们各自的出现次数。然后，统计这些用户会的语言的出现次数。最后，找出这些用户会的语言中出现次数最多的那个，教给不会这门语言的用户，使得所有好友之间都可以相互沟通。需要教的人数就是不会这门语言的用户数减去已经会这门语言的用户数。

时间复杂度: O(m*n + f*n)

空间复杂度: O(m*n + m + n)

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        # 将每个用户会的语言转换成集合
        tmp = [None] * len(languages)
        for i, langs in enumerate(languages):
            tmp[i] = set(langs)
        
        # 判断两个用户是否有共同语言
        def has_common(p1, p2):
            for lang1 in tmp[p1-1]:
                if lang1 in tmp[p2-1]:
                    return True
            return False
        
        # 统计没有共同语言的好友对中各自的出现次数
        p_cnt = Counter()
        for p1, p2 in friendships:
            if not has_common(p1, p2):
                p_cnt[p1] += 1
                p_cnt[p2] += 1
        
        if len(p_cnt) == 0:
            return 0
        
        # 统计这些用户会的语言的出现次数
        lang_cnt = Counter()
        for p, _ in p_cnt.items():
            for lang in languages[p - 1]:
                lang_cnt[lang] += 1
        
        # 找出出现次数最多的语言
        best_lang, cnt = lang_cnt.most_common(1)[0]
        return len(p_cnt) - cnt

Explore

在这个题解中，通过统计每种语言在不会共同语言的用户对中的出现频率来保证选择。首先识别出所有好友对中不共享任何语言的用户对，然后对这些用户统计他们各自所会的语言的出现次数。目标是选择一门语言，使得需要新学这门语言的用户数量最小。因此，选择出现次数最多的语言，意味着这门语言已经被最多的目标用户学会，从而教授这门语言的总人数会最少。这种策略在贪心算法的框架下是有效的，因为它每一步都尽可能减少需要教授的人数。

在实现`has_common`函数时，选择使用循环遍历的原因可能是出于效率的考虑。虽然使用集合的交集操作（如`set1 & set2`）可以直接判断两个集合是否有共同元素，但这种方法会产生一个新的集合，可能涉及额外的内存分配和计算开销。相反，循环遍历列表并检查元素是否存在于另一个集合中（使用`in`操作符），可以在找到第一个共同元素时立即停止，这样在最佳情况下可以更快地返回结果，尤其是当共同语言出现在列表的开始部分时。

在最后计算最少教授人数时，使用`len(p_cnt) - cnt`的方式基于以下前提条件：`p_cnt`记录的是所有需要通过教授新语言来实现沟通的用户数量（即没有共同语言的好友对中的用户），而`cnt`是这些用户中已经会某一特定语言（出现次数最多的语言）的用户数量。这样，`len(p_cnt) - cnt`实际上计算的是在已经确定最优语言之后，还需要被教授这门语言的用户数量。这种计算方式假设最优语言是能够最大程度减少教授需求的语言，即这种语言已经被尽可能多的目标用户掌握。