统计参与通信的服务器

难度: Medium

这里有一幅服务器分布图，服务器的位置标识在 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

Submission

运行时间: 40 ms

内存: 17.9 MB

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        out=0
        m,n=len(grid),len(grid[0])
        rowc=[-1]*n
        for i in range(m):
            k=sum(grid[i])
            if k==0: continue
            elif k>1:
                out+=k
                continue
            else:
                for j in range(n):
                    if grid[i][j]==1: break
                if rowc[j]==-1:
                    rowc[j]=0
                    for k in range(m):rowc[j]+=grid[k][j]
                if rowc[j]>1: out+=1
        return out

Explain

这个题解首先使用一个一维数组 rowc 来存储每一列的服务器总数。数组的初始值设为 -1，表示该列的服务器数量还未计算。对于网格中的每一行，先计算该行中服务器的数量。如果一行中的服务器数量大于1，表示这行的所有服务器都可以互相通信，直接将该行的服务器数量加到最终结果中。如果一行中只有一个服务器，需要检查这个服务器所在的列是否已经计算过服务器总数，如果未计算，则遍历该列统计服务器数量并更新 rowc 数组。如果该服务器所在的列的服务器总数大于1，则这台服务器可以与其他服务器通信，将结果加1。

时间复杂度: O(m * n)

空间复杂度: O(n)

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        out = 0  # 初始化可以通信的服务器数量
        m, n = len(grid), len(grid[0])  # 获取行列数
        rowc = [-1] * n  # 初始化列计数器，-1 表示未计算该列
        for i in range(m):  # 遍历每一行
            k = sum(grid[i])  # 计算当前行的服务器数量
            if k == 0: continue  # 如果没有服务器，跳过
            elif k > 1:  # 如果当前行的服务器数量大于1，它们可以互相通信
                out += k  # 增加输出计数
                continue
            else:  # 只有一个服务器的情况下
                for j in range(n):  # 查找这个服务器的列位置
                    if grid[i][j] == 1: break
                if rowc[j] == -1:  # 如果这列的服务器数量还未计算
                    rowc[j] = 0  # 初始化这列的服务器数量计数
                    for k in range(m): rowc[j] += grid[k][j]  # 计算这列的服务器总数
                if rowc[j] > 1: out += 1  # 如果列中的服务器数量大于1，这台服务器可以通信
        return out

Explore

在算法中，`rowc`数组用于存储每一列的服务器数量。初始化所有元素为-1的目的是作为一个标记，表示该列的服务器数量未被计算。这样，当算法遇到需要知道某一列的服务器数量时，如果对应的`rowc`值为-1，就知道需要遍历这个列来计算服务器数量，否则直接使用`rowc`数组中的值。这种做法避免了不必要的重复计算，提高了算法效率。

这种情况发生在当网格的某一行只有一个服务器，并且这个服务器所在的列的服务器数量尚未被计算时。在现有的算法实现中，每当遇到只有一个服务器的行，都可能需要遍历那个服务器所在的列来计算列的服务器总数。为了减少这种重复遍历，可以在算法一开始对所有列进行一次遍历，预先计算好每列的服务器数量，并存储在`rowc`数组中。这样，在处理每行数据时，就无需再次遍历列，直接从`rowc`中读取即可。虽然这增加了初始的计算开销，但避免了后续的重复遍历，特别是在大规模数据时，这种优化是有益的。

这样设计的主要原因是优化算法效率和处理逻辑的简化。当一行中的服务器数量大于1时，这行的所有服务器都可以互相通信，因此可以直接将该行的服务器数量累加到结果中。相反，如果一行只有一个服务器，需要额外检查该服务器是否能与其所在列的其他服务器通信（即该列的服务器总数是否大于1）。这种分开处理的方法让算法在遇到可以直接确定结果的情况下更快处理，同时对于需要额外检查的情况，能够具体问题具体分析。

代码中的双重循环方法虽然直观，但不是最优的。更高效的方法是，可以在算法的一开始就遍历整个网格一次，同时计算每一行和每一列的服务器数量，存储在两个数组中。这样，在后续的处理中，就无需再对列进行单独的遍历，可以直接使用预先计算好的列服务器数量。这种一次遍历预处理的方法减少了重复计算，提高了算法的整体效率，尤其是对于大规模数据集。