來源：力扣（LeetCode）
描述：
這里有一幅服務(wù)器分布圖，服務(wù)器的位置標識在 m * n 的整數(shù)矩陣網(wǎng)格 grid 中，1 表示單元格上有服務(wù)器，0 表示沒有。
如果兩臺服務(wù)器位于同一行或者同一列，我們就認為它們之間可以進行通信。
請你統(tǒng)計并返回能夠與至少一臺其他服務(wù)器進行通信的服務(wù)器的數(shù)量。
示例 1：
輸入：grid = [[1,0],[0,1]]
輸出：0
解釋：沒有一臺服務(wù)器能與其他服務(wù)器進行通信。
示例 2：
輸入：grid = [[1,0],[1,1]]
輸出：3
解釋：所有這些服務(wù)器都至少可以與一臺別的服務(wù)器進行通信。
示例 3：
輸入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
輸出：4
解釋：第一行的兩臺服務(wù)器互相通信，第三列的兩臺服務(wù)器互相通信，但右下角的服務(wù)器無法與其他服務(wù)器通信。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m <= 250
- 1 <= n <= 250
- grid[i][j] == 0 or 1
方法：兩次遍歷 + 哈希表
思路與算法
我們可以使用兩次遍歷解決本題。
在第一次遍歷中，我們遍歷數(shù)組 grid，如果 grid[i, j] 的值為 1，說明位置 (i, j) 有一臺服務(wù)器，我們可以將第 i 行服務(wù)器的數(shù)量，以及第 j 行服務(wù)器的數(shù)量，均加上 1。為了維護行列中服務(wù)器的數(shù)量，我們可以使用兩個哈希映射 row 和 col，row 中存儲行的編號以及每一行服務(wù)器的數(shù)量，col 存儲列的編號以及每一列服務(wù)器的數(shù)量。
在第二次遍歷中，我們就可以根據(jù) row 和 col 來判斷每一臺服務(wù)器是否能與至少其它一臺服務(wù)器進行通信了。如果 grid(i, j) 的值為 1，并且 row[i] 和 col[j] 中至少有一個嚴格大于 1，就說明位置 (i, j) 的服務(wù)器能與同一行或者同一列的另一臺服務(wù)器進行通信，答案加 1。
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-670171.html
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
unordered_map<int, int> rows, cols;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++rows[i];
++cols[j];
}
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
++ans;
}
}
}
return ans;
}
};
時間 48ms 擊敗 66.06%使用 C++ 的用戶
內(nèi)存 21.43MB 擊敗 23.03%使用 C++ 的用戶
復雜度分析文章來源地址http://www.zghlxwxcb.cn/news/detail-670171.html
- 時間復雜度：O(mn)。
- 空間復雜度：O(m+n)，即為哈希映射需要使用的空間。
author：力扣官方題解
到了這里，關(guān)于【1267. 統(tǒng)計參與通信的服務(wù)器】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
