【数组】B_1267. 统计参与通信的服务器（枚举 / 并查集）
一、题目描述
A1，错误解释：矩形有 m 行，n 列，但并查集的 id 数组只有一行，故 0,...,m,m+1,...,m+n−10, ... , m, m+1 , ..., m+n-10,...,m,m+1,...,m+n−1 表示示 id 数组的值，故此处
作者：wnjkhd
You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.
Return the number of servers that communicate with any other server.
Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
二、题解
方法一：枚举
同一行和同一列必须要有两台或以上的计算机才能互相通信。
也就是说某一个位置所在行和列只有一台 PC 的话，是无法互相通信的。
public int countServers(int[][] grid) {
int R = grid.length, C = grid[0].length;
int[] row = new int[R];
int[] col = new int[C];
int res = 0;
for (int x = 0; x < R; x++)
for (int y = 0; y < C; y++) {
if (grid[x][y] == 1) {
row[x]++; col[y]++;
res++;
}
}
for (int x = 0; x < R; x++)
for (int y = 0; y < C; y++) {
if (grid[x][y] == 1 && row[x] == 1 && col[y] == 1) {
res--;
}
}
return res;
}
复杂度分析
时间复杂度：O(R×C)O(R × C)O(R×C)，
空间复杂度：O(R×C)O(R × C)O(R×C)，
方法二：并查集
如果遇到某一个格子是 1，那么就合并其所在行和列，并且 count++。
最后，在并查集 uf 中查找某一个结点下只有一个孩子，如果有，证明这个 pc 是独立的，count--。
Q&A
Q1：为什么合并行和列是union(i, j+row)？A1，错误解释：矩形有 m 行，n 列，但并查集的 id 数组只有一行，故 0,...,m,m+1,...,m+n−10, ... , m, m+1 , ..., m+n-10,...,m,m+1,...,m+n−1 表示示 id 数组的值，故此处
j + m 表示 i 行 j 列在 id 数组中的索引。
int R, C;
public int countServers(int[][] grid) {
R = grid.length; C = grid[0].length;
int tot = 0;
UF uf = new UF(R + C);
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (grid[i][j] == 1) {
tot++;
uf.union(i, j+R);
}
}
Map map = new HashMap();
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (grid[i][j] == 1) {
int p = uf.find(i);
map.put(p, map.getOrDefault(p, 0)+1);
}
}
for (int k : map.keySet()) {
if (map.get(k) == 1)
tot--;
}
return tot;
}
class UF {
int[] id;
int count;
public UF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
public int find(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}
public boolean isConn(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID) {
return;
}
id[pID] = qID;
count--;
}
}
复杂度分析
时间复杂度：O()O()O()，
空间复杂度：O()O()O()，
作者：wnjkhd
相关文章
Fredrica
2020-11-10
Maha
2021-04-02
Leona
2020-07-12
Bena
2020-04-26
Manda
2020-04-28
Alexandra
2023-07-20
Mathilda
2023-07-21
Lark
2023-07-21
Dianthe
2023-07-21
Ebony
2023-07-21
Olive
2023-07-21
Glory
2023-07-21
Keelia
2023-07-21
Raizel
2023-07-21
Janna
2023-07-22
Rhea
2023-07-22
Aurora
2023-07-22
Rosine
2023-07-22
Bena
2023-07-22
Rhoda
2023-07-22