统计参与通信的服务器
难度:
标签:
题目描述
这里有一幅服务器分布图,服务器的位置标识在 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
代码结果
运行时间: 40 ms, 内存: 17.9 MB
/*
* 思路:
* 1. 使用Java Stream API进行行和列的遍历,并统计每行和每列的服务器数量。
* 2. 再次遍历矩阵,使用Stream判断每个服务器是否能与其他服务器通信。
* 3. 统计能够与至少一台其他服务器进行通信的服务器数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int countServers(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] rowCount = new int[m];
int[] colCount = new int[n];
// 计算每一行和每一列的服务器数量
IntStream.range(0, m).forEach(i -> IntStream.range(0, n).forEach(j -> {
if (grid[i][j] == 1) {
rowCount[i]++;
colCount[j]++;
}
}));
// 统计能够与至少一台其他服务器进行通信的服务器数量
return (int) IntStream.range(0, m).flatMap(i -> IntStream.range(0, n).filter(j -> grid[i][j] == 1 && (rowCount[i] > 1 || colCount[j] > 1))).count();
}
}
解释
方法:
这个题解首先使用一个一维数组 rowc 来存储每一列的服务器总数。数组的初始值设为 -1,表示该列的服务器数量还未计算。对于网格中的每一行,先计算该行中服务器的数量。如果一行中的服务器数量大于1,表示这行的所有服务器都可以互相通信,直接将该行的服务器数量加到最终结果中。如果一行中只有一个服务器,需要检查这个服务器所在的列是否已经计算过服务器总数,如果未计算,则遍历该列统计服务器数量并更新 rowc 数组。如果该服务器所在的列的服务器总数大于1,则这台服务器可以与其他服务器通信,将结果加1。
时间复杂度:
O(m * n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法实现中,为什么初始化列计数器`rowc`数组的所有元素为-1?这里的-1具体代表什么含义?
▷🦆
在解释中提到,对于每一个单独的服务器,还需要检查其对应的列,这在最坏情况下可能需要再次遍历整个列。请问这种情况是如何发生的?能否通过优化减少这种重复遍历的情况?
▷🦆
算法中将行中服务器数量大于1时的处理和只有一个服务器时的处理区分开来了,请问这样设计的原因是什么?
▷🦆
代码中使用了双重循环遍历行和列来计算列中的服务器数量(当`rowc[j]`为-1时),这种方法是否最优?存在更高效的方法来处理这个问题吗?
▷