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 或 1

解题思路

这道题的核心思想是找出能够与其他服务器通信的服务器数量。两台服务器可以通信的条件是它们在同一行或同一列。

解法一：统计行列服务器数量（推荐）

  1. 首先统计每一行和每一列的服务器数量
  2. 遍历网格，对于每个服务器位置 (i, j)：
    • 如果该行的服务器数量 > 1 或该列的服务器数量 > 1，说明该服务器能与其他服务器通信
    • 将这样的服务器计入结果

解法二：并查集 可以使用并查集将同行或同列的服务器连接起来，最后统计连通分量大小大于1的服务器数量。但这种方法相对复杂，时空开销较大。

解法三：DFS/BFS 对每个服务器进行搜索，找到所有与它连通的服务器。但这种方法也比较复杂。

第一种解法最为简洁高效，只需要两次遍历即可完成，是最优解法。

代码实现

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> rowCount(m, 0), colCount(n, 0);
        
        // 统计每行每列的服务器数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }
        
        int result = 0;
        // 统计能通信的服务器
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && (rowCount[i] > 1 || colCount[j] > 1)) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row_count = [0] * m
        col_count = [0] * n
        
        # 统计每行每列的服务器数量
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1
        
        result = 0
        # 统计能通信的服务器
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (row_count[i] > 1 or col_count[j] > 1):
                    result += 1
        
        return result

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];
        
        // 统计每行每列的服务器数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }
        
        int result = 0;
        // 统计能通信的服务器
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && (rowCount[i] > 1 || colCount[j] > 1)) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

var countServers = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    const rowCount = new Array(m).fill(0);
    const colCount = new Array(n).fill(0);
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                rowCount[i]++;
                colCount[j]++;
            }
        }
    }
    
    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1 && (rowCount[i] > 1 || colCount[j] > 1)) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m×n)
空间复杂度O(m+n)

其中 m 是网格的行数，n 是网格的列数。我们需要遍历网格两次，每次都是 O(m×n)，额外使用了两个数组分别存储每行和每列的服务器数量。