题目描述
这里有一幅服务器分布图,服务器的位置标识在 m * n
的整数矩阵网格 grid
中,1 表示单元格上有服务器,0 表示没有。
如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。
请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
样例
输入:grid = [[1,0],[0,1]]
输出:0
解释:没有一台服务器能与其他服务器进行通信。
输入:grid = [[1,0],[1,1]]
输出:3
解释:所有这些服务器都至少可以与一台别的服务器进行通信。
输入:grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出:4
解释:第一行的两台服务器互相通信,第三列的两台服务器互相通信,但右下角的服务器无法与其他服务器通信。
限制
m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 或 1
算法
(暴力枚举) $O(mn)$
- 对于每一行,统计这一行中
1
位置的个数。如果个数大于 1,则修改1
的位置为2
。 - 对于每一列,统计这一列中
1
或2
位置的个数。如果个数大于 1,则修改1
的位置为2
。 - 最后统计位置为
2
的个数。
时间复杂度
- 每个位置被遍历常数次,故时间复杂度为 $O(mn)$。
空间复杂度
- 仅需要常数的空间
C++ 代码
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
int cnt = 0;
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
cnt++;
if (cnt > 1) {
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
grid[i][j] = 2;
}
}
for (int j = 0; j < n; j++) {
int cnt = 0;
for (int i = 0; i < m; i++)
if (grid[i][j] >= 1)
cnt++;
if (cnt > 1)
for (int i = 0; i < m; i++)
if (grid[i][j] == 1)
grid[i][j] = 2;
}
int ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 2)
ans++;
return ans;
}
};