Python程序：查找教授课程所需的最小人数

假设我们有一个数字n，一个名为“languages”的数组和一个名为“friendships”的数组，因此有n种语言，编号从1到n，“languages[i]”表示第i个用户知道的语言集，“friendships[i]”包含一对[ui, vi]，表示用户ui和vi之间的友谊关系。我们可以选择一种语言并教授给一些用户，以便所有朋友都可以互相交流。我们必须找到需要教授的最小用户数。（有一点需要注意的是，友谊关系不是传递的，所以如果x是y的朋友，y是z的朋友，这并不意味着x是z的朋友）。

因此，如果输入类似于n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]]，则输出将为2，因为我们需要训练语言3给用户1和3，因为有两个用户需要教授，所以输出为2。

为了解决这个问题，我们将遵循以下步骤：

• lang := 所有用户已知语言的不同集合的列表
• not_comm := 一个新的集合
• 对于friendships中的每一对a, b，执行以下操作：
  • a := a - 1
  • b := b - 1
  • 如果lang[a]和lang[b]是不相交的，则
    • 将a插入not_comm
    • 将b插入not_comm
• 如果not_comm为空，则
  • 返回0
• cnt := 一个空映射
• 对于not_comm中的每个人，执行以下操作：
  • 存储lang[person]的频率并将其存储到cnt中
• temp := cnt所有值的列表中的最大值
• 返回not_comm的大小 - temp

示例

让我们看看以下实现以获得更好的理解：

from collections import Counter
def solve(n, languages, friendships):
   lang = [set(L) for L in languages]

   not_comm = set()
   for a,b in friendships:
      a -= 1
      b -= 1
      if lang[a].isdisjoint(lang[b]):
         not_comm.add(a)
         not_comm.add(b)
   if not not_comm:
      return 0

   cnt = Counter()
   for person in not_comm:
      cnt.update(lang[person])
   temp = max(cnt.values())
   return len(not_comm) - temp

n = 3
languages = [[2],[1,3],[1,2],[3]]
friendships = [[1,4],[1,2],[3,4],[2,3]]
print(solve(n, languages, friendships))

输入

3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]

输出

2

Arnab Chakraborty

更新于: 2021年10月7日

138 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习