1. 问题概述与理解

今天我们来拆解LeetCode第1267题"统计参与通信的服务器"。这是一道中等难度的矩阵遍历问题，考察我们对二维数组的处理能力和空间优化意识。题目描述如下：

给定一个m×n的矩阵grid，其中grid[i][j]表示第i行第j列单元格中的服务器状态：

• grid[i][j] = 1表示该位置有一台服务器
• grid[i][j] = 0表示该位置为空

服务器可以与其他同一行或者同一列上的任意一台服务器通信。我们需要统计能够与至少一台其他服务器通信的服务器总数。

注意：服务器不能与自己通信，即如果某行或列只有一台服务器，它无法与自己通信，因此不计入结果

2. 解题思路分析

2.1 暴力解法与优化方向

最直观的暴力解法是：对于每个服务器(grid[i][j] == 1)，检查其所在行和列是否有其他服务器。这种方法的时间复杂度是O(mn*(m+n))，对于较大的矩阵效率极低。

优化方向很明确：我们需要避免重复计算行和列的服务器数量。可以预先统计每行和每列的服务器总数，这样在判断某个服务器是否能通信时，只需要查询预计算的结果即可。

2.2 空间换时间策略

我们可以采用"空间换时间"的策略：

1. 创建两个数组rows和cols，分别记录每行和每列的服务器数量
2. 第一次遍历矩阵，填充rows和cols数组
3. 第二次遍历矩阵，对于每个服务器，检查rows[i] > 1或cols[j] > 1

这种方法将时间复杂度降低到O(mn)，空间复杂度为O(m+n)，是典型的预处理优化案例。

3. 代码实现与细节

3.1 Python实现

def countServers(grid): m, n = len(grid), len(grid[0]) rows = [0] * m cols = [0] * n # 第一次遍历统计行列服务器数 for i in range(m): for j in range(n): if grid[i][j] == 1: rows[i] += 1 cols[j] += 1 # 第二次遍历统计可通信服务器 res = 0 for i in range(m): for j in range(n): if grid[i][j] == 1 and (rows[i] > 1 or cols[j] > 1): res += 1 return res

3.2 关键细节解析

1. 边界条件处理：代码自动处理了m=0或n=0的情况，因为range(0)不会执行循环
2. 服务器判断：只有当grid[i][j]==1时才进行统计和判断
3. 通信条件：rows[i]>1或cols[j]>1表示该服务器所在行或列有其他服务器
4. 空间优化：仅使用O(m+n)的额外空间，这在m和n较大时非常关键

4. 复杂度分析与优化验证

4.1 时间复杂度

• 两次完整的矩阵遍历：2*O(mn) = O(mn)
• 每次遍历中的操作都是O(1)的简单判断和累加
• 整体时间复杂度严格保持在O(mn)

4.2 空间复杂度

• rows数组：O(m)
• cols数组：O(n)
• 其他变量：O(1)
• 总空间复杂度：O(m+n)

4.3 极端情况测试

1. 全0矩阵：应返回0
2. 全1矩阵：应返回m*n（所有服务器都能通信）
3. 每行每列只有1个服务器：应返回0（无法通信）
4. 单行或单列矩阵：边界条件处理正确

5. 常见错误与调试技巧

5.1 典型错误模式

1. 忘记检查服务器自身：

   # 错误写法：忽略了服务器不能与自己通信的条件 if grid[i][j] == 1 and (rows[i] >= 1 or cols[j] >= 1):

2. 行列统计混淆：

   # 错误写法：行列索引用反 rows[j] += 1 # 应该是rows[i] cols[i] += 1 # 应该是cols[j]

3. 单次遍历尝试：有人试图在一次遍历中完成统计和判断，这会遗漏后续服务器的信息

5.2 调试技巧

1. 打印中间结果：在第一次遍历后打印rows和cols数组，验证统计是否正确
2. 小规模测试：先用3x3等小矩阵手动计算预期结果
3. 边界测试：专门测试m=1或n=1的情况
4. 性能分析：对于大矩阵(如500x500)，检查运行时间是否线性增长

6. 算法扩展与变种

6.1 相似题目推荐

1. LeetCode 661. 图片平滑器：类似的矩阵遍历问题
2. LeetCode 73. 矩阵置零：需要行列统计的矩阵问题
3. LeetCode 54. 螺旋矩阵：更复杂的矩阵遍历方式

6.2 问题变种思考

如果题目改为：

• 统计不能通信的服务器数量？
  • 解法：总服务器数 - 能通信的服务器数
• 只统计通过行通信的服务器？
  • 修改条件为rows[i]>1且cols[j]<=1
• 服务器可以斜对角通信？
  • 需要增加对角线方向的统计

7. 实际应用场景

这类矩阵行列统计问题在实际中有广泛应用：

1. 分布式系统：统计可以互相通信的计算节点
2. 图像处理：检测像素的行列相关性
3. 社交网络：分析用户之间的关系连接
4. 硬件设计：电路板上的元件连接检查

8. 个人解题心得

在解决这个问题时，我有几点深刻体会：

1. 预处理是优化关键：很多矩阵问题都可以通过预先统计行列信息来优化
2. 空间换时间的权衡：O(m+n)的额外空间在大多数情况下是可以接受的
3. 边界条件的重要性：特别是m或n为1时的特殊情况需要仔细考虑
4. 两次遍历的必然性：有些优化试图合并遍历，但可能适得其反

一个实用的调试技巧是：当不确定算法是否正确时，先用暴力解法实现作为基准，再逐步优化，这样可以验证优化后的结果是否正确。