題目

在一個由 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、雜湊輔助；時間複雜度O(n^2)，空間複雜度O(n^2)

func minimumTeachings(n int, languages [][]int, friendships [][]int) int {	m := make(map[int]map[int]int)	for i := 0; i < len(languages); i++ {		a := i + 1		m[a] = make(map[int]int)		for j := 0; j < len(languages[i]); j++ {			b := languages[i][j]			m[a][b] = 1		}	}	need := make(map[int]bool) // 需要溝通的人列表	for i := 0; i < len(friendships); i++ {		a, b := friendships[i][0], friendships[i][1]		flag := false		for j := 1; j <= n; j++ {			if m[a][j] == 1 && m[b][j] == 1 {				flag = true				break			}		}		if flag == false {			need[a] = true			need[b] = true		}	}	res := 0	for i := 1; i <= n; i++ {		count := 0		for k := range need {			if m[k][i] == 1 {				count++			}		}		if count > res {			res = count		}	}	return len(need) - res}

總結

Medium題目，記錄不能溝通的人列表，然後嘗試不同語言，統計會某語言最多的人數，最後需要溝通的人數減去最多的人數即可。