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*(mn))对于较大的矩阵效率极低。优化方向很明确我们需要避免重复计算行和列的服务器数量。可以预先统计每行和每列的服务器总数这样在判断某个服务器是否能通信时只需要查询预计算的结果即可。2.2 空间换时间策略我们可以采用空间换时间的策略创建两个数组rows和cols分别记录每行和每列的服务器数量第一次遍历矩阵填充rows和cols数组第二次遍历矩阵对于每个服务器检查rows[i] 1或cols[j] 1这种方法将时间复杂度降低到O(mn)空间复杂度为O(mn)是典型的预处理优化案例。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 res3.2 关键细节解析边界条件处理代码自动处理了m0或n0的情况因为range(0)不会执行循环服务器判断只有当grid[i][j]1时才进行统计和判断通信条件rows[i]1或cols[j]1表示该服务器所在行或列有其他服务器空间优化仅使用O(mn)的额外空间这在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(mn)4.3 极端情况测试全0矩阵应返回0全1矩阵应返回m*n所有服务器都能通信每行每列只有1个服务器应返回0无法通信单行或单列矩阵边界条件处理正确5. 常见错误与调试技巧5.1 典型错误模式忘记检查服务器自身# 错误写法忽略了服务器不能与自己通信的条件 if grid[i][j] 1 and (rows[i] 1 or cols[j] 1):行列统计混淆# 错误写法行列索引用反 rows[j] 1 # 应该是rows[i] cols[i] 1 # 应该是cols[j]单次遍历尝试有人试图在一次遍历中完成统计和判断这会遗漏后续服务器的信息5.2 调试技巧打印中间结果在第一次遍历后打印rows和cols数组验证统计是否正确小规模测试先用3x3等小矩阵手动计算预期结果边界测试专门测试m1或n1的情况性能分析对于大矩阵(如500x500)检查运行时间是否线性增长6. 算法扩展与变种6.1 相似题目推荐LeetCode 661. 图片平滑器类似的矩阵遍历问题LeetCode 73. 矩阵置零需要行列统计的矩阵问题LeetCode 54. 螺旋矩阵更复杂的矩阵遍历方式6.2 问题变种思考如果题目改为统计不能通信的服务器数量解法总服务器数 - 能通信的服务器数只统计通过行通信的服务器修改条件为rows[i]1且cols[j]1服务器可以斜对角通信需要增加对角线方向的统计7. 实际应用场景这类矩阵行列统计问题在实际中有广泛应用分布式系统统计可以互相通信的计算节点图像处理检测像素的行列相关性社交网络分析用户之间的关系连接硬件设计电路板上的元件连接检查8. 个人解题心得在解决这个问题时我有几点深刻体会预处理是优化关键很多矩阵问题都可以通过预先统计行列信息来优化空间换时间的权衡O(mn)的额外空间在大多数情况下是可以接受的边界条件的重要性特别是m或n为1时的特殊情况需要仔细考虑两次遍历的必然性有些优化试图合并遍历但可能适得其反一个实用的调试技巧是当不确定算法是否正确时先用暴力解法实现作为基准再逐步优化这样可以验证优化后的结果是否正确。