Medium

题目描述

在一个由 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 <= 500
  • languages.length == m
  • 1 <= m <= 500
  • 1 <= languages[i].length <= n
  • 1 <= languages[i][j] <= n
  • 1 <= ui < vi <= languages.length
  • 1 <= friendships.length <= 500
  • 所有元组 (ui, vi) 都是唯一的
  • languages[i] 只包含唯一值

解题思路

这是一道贪心算法题目，核心思路是找到教授哪种语言能使需要教授的人数最少。

解题思路：

  1. 识别无法沟通的朋友对：首先遍历所有友谊关系，找出哪些朋友对之间没有共同语言，这些朋友对无法直接沟通。

  2. 暴力枚举每种语言：对于每种可能的语言（1到n），计算如果选择这种语言作为教授语言，需要教授多少人。

  3. 计算教授成本：对于每种语言，找出所有无法沟通的朋友对中，有多少人不会这种语言。这些人就是需要教授的对象。注意同一个人可能出现在多个朋友对中，但只需要教授一次。

  4. 选择最优方案：选择需要教授人数最少的语言。

算法步骤：

  • 将每个用户的语言转换为集合，便于快速查找
  • 找出所有无法沟通的朋友对
  • 对每种语言，统计在无法沟通的朋友对中，不会该语言的用户数量
  • 返回最小的教授人数

时间复杂度主要来自于枚举语言和统计用户，整体是可接受的。

代码实现

class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        int m = languages.size();
        
        // 将语言列表转换为集合，便于快速查找
        vector<unordered_set<int>> langSet(m);
        for (int i = 0; i < m; i++) {
            for (int lang : languages[i]) {
                langSet[i].insert(lang);
            }
        }
        
        // 找出无法沟通的朋友对
        vector<pair<int, int>> cannotCommunicate;
        for (auto& friendship : friendships) {
            int u = friendship[0] - 1, v = friendship[1] - 1; // 转换为0索引
            
            // 检查是否有共同语言
            bool hasCommonLang = false;
            for (int lang : langSet[u]) {
                if (langSet[v].count(lang)) {
                    hasCommonLang = true;
                    break;
                }
            }
            
            if (!hasCommonLang) {
                cannotCommunicate.push_back({u, v});
            }
        }
        
        // 如果所有朋友都能沟通，则不需要教授任何人
        if (cannotCommunicate.empty()) return 0;
        
        int minTeach = m + 1;
        
        // 尝试每种语言
        for (int lang = 1; lang <= n; lang++) {
            unordered_set<int> needTeach;
            
            // 对于每个无法沟通的朋友对
            for (auto& pair : cannotCommunicate) {
                int u = pair.first, v = pair.second;
                
                // 如果用户u不会这种语言，需要教授
                if (langSet[u].find(lang) == langSet[u].end()) {
                    needTeach.insert(u);
                }
                // 如果用户v不会这种语言，需要教授
                if (langSet[v].find(lang) == langSet[v].end()) {
                    needTeach.insert(v);
                }
            }
            
            minTeach = min(minTeach, (int)needTeach.size());
        }
        
        return minTeach;
    }
};

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        m = len(languages)
        
        # 将语言列表转换为集合，便于快速查找
        lang_sets = [set(langs) for langs in languages]
        
        # 找出无法沟通的朋友对
        cannot_communicate = []
        for u, v in friendships:
            u, v = u - 1, v - 1  # 转换为0索引
            
            # 检查是否有共同语言
            if not (lang_sets[u] & lang_sets[v]):
                cannot_communicate.append((u, v))
        
        # 如果所有朋友都能沟通，则不需要教授任何人
        if not cannot_communicate:
            return 0
        
        min_teach = m + 1
        
        # 尝试每种语言
        for lang in range(1, n + 1):
            need_teach = set()
            
            # 对于每个无法沟通的朋友对
            for u, v in cannot_communicate:
                # 如果用户u不会这种语言，需要教授
                if lang not in lang_sets[u]:
                    need_teach.add(u)
                # 如果用户v不会这种语言，需要教授
                if lang not in lang_sets[v]:
                    need_teach.add(v)
            
            min_teach = min(min_teach, len(need_teach))
        
        return min_teach

public class Solution {
    public int MinimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.Length;
        
        // 将语言列表转换为集合，便于快速查找
        HashSet<int>[] langSets = new HashSet<int>[m];
        for (int i = 0; i < m; i++) {
            langSets[i] = new HashSet<int>(languages[i]);
        }
        
        // 找出无法沟通的朋友对
        List<(int, int)> cannotCommunicate = new List<(int, int)>();
        foreach (var friendship in friendships) {
            int u = friendship[0] - 1, v = friendship[1] - 1; // 转换为0索引
            
            // 检查是否有共同语言
            bool hasCommonLang = false;
            foreach (int lang in langSets[u]) {
                if (langSets[v].Contains(lang)) {
                    hasCommonLang = true;
                    break;
                }
            }
            
            if (!hasCommonLang) {
                cannotCommunicate.Add((u, v));
            }
        }
        
        // 如果所有朋友都能沟通，则不需要教授任何人
        if (cannotCommunicate.Count == 0) return 0;
        
        int minTeach = m + 1;
        
        // 尝试每种语言
        for (int lang = 1; lang <= n; lang++) {
            HashSet<int> needTeach = new HashSet<int>();
            
            // 对于每个无法沟通的朋友对
            foreach (var (u, v) in cannotCommunicate) {
                // 如果用户u不会这种语言，需要教授
                if (!langSets[u].Contains(lang)) {
                    needTeach.Add(u);
                }
                // 如果用户v不会这种语言，需要教授
                if (!langSets[v].Contains(lang)) {
                    needTeach.Add(v);
                }
            }
            
            minTeach = Math.Min(minTeach, needTeach.Count);
        }
        
        return minTeach;
    }
}

/**
 * @param {number} n
 * @param {number[][]} languages
 * @param {number[][]} friendships
 * @return {number}
 */
var minimumTeachings = function(n, languages, friendships) {
    const langSets = languages.map(langs => new Set(langs));
    
    // Find friendships that can't communicate
    const problematicFriendships = [];
    for (const [u, v] of friendships) {
        const uLangs = langSets[u - 1];
        const vLangs = langSets[v - 1];
        let canCommunicate = false;
        
        for (const lang of uLangs) {
            if (vLangs.has(lang)) {
                canCommunicate = true;
                break;
            }
        }
        
        if (!canCommunicate) {
            problematicFriendships.push([u - 1, v - 1]);
        }
    }
    
    if (problematicFriendships.length === 0) return 0;
    
    // Get all users involved in problematic friendships
    const problematicUsers = new Set();
    for (const [u, v] of problematicFriendships) {
        problematicUsers.add(u);
        problematicUsers.add(v);
    }
    
    let minTeachings = problematicUsers.size;
    
    // Try teaching each language
    for (let lang = 1; lang <= n; lang++) {
        const usersToTeach = new Set();
        
        for (const [u, v] of problematicFriendships) {
            const uKnowsLang = langSets[u].has(lang);
            const vKnowsLang = langSets[v].has(lang);
            
            if (!uKnowsLang) usersToTeach.add(u);
            if (!vKnowsLang) usersToTeach.add(v);
        }
        
        minTeachings = Math.min(minTeachings, usersToTeach.size);
    }
    
    return minTeachings;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(F × L + n × F × m)，其中 F 是友谊关系数量，L 是平均语言数量，m 是用户数量。第一部分是找无法沟通的朋友对，第二部分是枚举语言计算教授成本
空间复杂度O(m × L + F)，用于存储语言集合和无法沟通的朋友对列表