题目描述
这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。
如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。
请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
样例
样例1
输入:grid = [[1,0],[0,1]]
输出:0
解释:没有一台服务器能与其他服务器进行通信。
样例2
输入:grid = [[1,0],[1,1]]
输出:3
解释:所有这些服务器都至少可以与一台别的服务器进行通信。
样例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 or 1
算法1
单独计算同行 同列的元素计数 大于等于2 则算作可互相通讯
C++ 代码
class Solution {
public:
set<vector<int>> resultSet;
int countServers(vector<vector<int>>& grid) {
for (int i = 0; i < grid.size(); i++) {
int firstx = -1; int firsty = -1;
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
if (firstx == -1) {
firstx = i; firsty = j;
}
else {
vector<int>v1{ firstx, firsty };
resultSet.insert(v1);
vector<int>v2{ i, j };
resultSet.insert(v2);
}
}
}
}
for (int y = 0; y < grid[0].size(); y++) {
int firstx = -1; int firsty = -1;
for (int x = 0; x < grid.size(); x++) {
if (grid[x][y] == 1) {
if (firstx == -1) {
firstx = x; firsty = y;
}
else {
vector<int>v1{ firstx, firsty };
resultSet.insert(v1);
vector<int>v2{ x, y };
resultSet.insert(v2);
}
}
}
}
return resultSet.size();
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla