题目描述
给你一个二维整数数组 properties，其维度为 n x m，以及一个整数 k。
定义一个函数 intersect(a, b)，它返回数组 a 和 b 中 共有的不同整数的数量 。
构造一个 无向图，其中每个索引 i 对应 properties[i]。如果且仅当 intersect(properties[i], properties[j]) >= k（其中 i 和 j 的范围为 [0, n - 1] 且 i != j），节点 i 和节点 j 之间有一条边。
返回结果图中 连通分量 的数量。
示例 1：
输入： properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1
输出： 3
解释：
生成的图有 3 个连通分量：
示例 2：
输入： properties = [[1,2,3],[2,3,4],[4,3,5]], k = 2
输出： 1
解释：
生成的图有 1 个连通分量：
示例 3：
输入： properties = [[1,1],[1,1]], k = 2
输出： 2
解释：
intersect(properties[0], properties[1]) = 1，小于 k。因此在图中 properties[0] 和 properties[1] 之间没有边。
提示：
1 <= n == properties.length <= 1001 <= m == properties[i].length <= 1001 <= properties[i][j] <= 1001 <= k <= m
解法
方法一：哈希表 + DFS
我们先将每个属性数组转换为一个哈希表，存储在哈希表数组 \(\textit{ss}\) 中。定义一个图 \(\textit{g}\)，其中 \(\textit{g}[i]\) 存储了与属性数组 \(\textit{properties}[i]\) 有边相连的属性数组的索引。
然后我们遍历所有的属性哈希表，对于每一对属性哈希表 \((i, j)\)，其中 \(j < i\)，我们检查这两个属性哈希表中的交集元素个数是否大于等于 \(k\)，如果是，则在图 \(\textit{g}\) 中添加一条从 \(i\) 到 \(j\) 的边，同时在图 \(\textit{g}\) 中添加一条从 \(j\) 到 \(i\) 的边。
最后，我们使用深度优先搜索计算图 \(\textit{g}\) 的连通分量的数量。
时间复杂度 \(O(n^2 \times m)\)，空间复杂度 \(O(n \times m)\)。其中 \(n\) 是属性数组的长度，而 \(m\) 是属性数组中的元素个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
def dfs(i: int) -> None:
vis[i] = True
for j in g[i]:
if not vis[j]:
dfs(j)
n = len(properties)
ss = list(map(set, properties))
g = [[] for _ in range(n)]
for i, s1 in enumerate(ss):
for j in range(i):
s2 = ss[j]
if len(s1 & s2) >= k:
g[i].append(j)
g[j].append(i)
ans = 0
vis = [False] * n
for i in range(n):
if not vis[i]:
dfs(i)
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 | class Solution {
private List<Integer>[] g;
private boolean[] vis;
public int numberOfComponents(int[][] properties, int k) {
int n = properties.length;
g = new List[n];
Set<Integer>[] ss = new Set[n];
Arrays.setAll(g, i -> new ArrayList<>());
Arrays.setAll(ss, i -> new HashSet<>());
for (int i = 0; i < n; ++i) {
for (int x : properties[i]) {
ss[i].add(x);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int cnt = 0;
for (int x : ss[i]) {
if (ss[j].contains(x)) {
++cnt;
}
}
if (cnt >= k) {
g[i].add(j);
g[j].add(i);
}
}
}
int ans = 0;
vis = new boolean[n];
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
++ans;
}
}
return ans;
}
private void dfs(int i) {
vis[i] = true;
for (int j : g[i]) {
if (!vis[j]) {
dfs(j);
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | class Solution {
public:
int numberOfComponents(vector<vector<int>>& properties, int k) {
int n = properties.size();
unordered_set<int> ss[n];
vector<int> g[n];
for (int i = 0; i < n; ++i) {
for (int x : properties[i]) {
ss[i].insert(x);
}
}
for (int i = 0; i < n; ++i) {
auto& s1 = ss[i];
for (int j = 0; j < i; ++j) {
auto& s2 = ss[j];
int cnt = 0;
for (int x : s1) {
if (s2.contains(x)) {
++cnt;
}
}
if (cnt >= k) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
int ans = 0;
vector<bool> vis(n);
auto dfs = [&](this auto&& dfs, int i) -> void {
vis[i] = true;
for (int j : g[i]) {
if (!vis[j]) {
dfs(j);
}
}
};
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
++ans;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | func numberOfComponents(properties [][]int, k int) (ans int) {
n := len(properties)
ss := make([]map[int]struct{}, n)
g := make([][]int, n)
for i := 0; i < n; i++ {
ss[i] = make(map[int]struct{})
for _, x := range properties[i] {
ss[i][x] = struct{}{}
}
}
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
cnt := 0
for x := range ss[i] {
if _, ok := ss[j][x]; ok {
cnt++
}
}
if cnt >= k {
g[i] = append(g[i], j)
g[j] = append(g[j], i)
}
}
}
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
vis[i] = true
for _, j := range g[i] {
if !vis[j] {
dfs(j)
}
}
}
for i := 0; i < n; i++ {
if !vis[i] {
dfs(i)
ans++
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | function numberOfComponents(properties: number[][], k: number): number {
const n = properties.length;
const ss: Set<number>[] = Array.from({ length: n }, () => new Set());
const g: number[][] = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
for (const x of properties[i]) {
ss[i].add(x);
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
let cnt = 0;
for (const x of ss[i]) {
if (ss[j].has(x)) {
cnt++;
}
}
if (cnt >= k) {
g[i].push(j);
g[j].push(i);
}
}
}
let ans = 0;
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
vis[i] = true;
for (const j of g[i]) {
if (!vis[j]) {
dfs(j);
}
}
};
for (let i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i);
ans++;
}
}
return ans;
}
|