題目描述: 給定一個 m × n 的二維網格 grid,其中 1 代表伺服器,0 代表空位。如果兩台伺服器位於同一行或同一列,它們就可以通訊。請計算能夠與至少一台其他伺服器通訊的伺服器數量。
解題思路: 首先統計每一行和每一列中伺服器的數量。然後再次遍歷網格,對於每個伺服器位置 (i, j),如果該行或該列的伺服器數量大於 1,則這台伺服器可以與其他伺服器通訊。這個方法利用了一個關鍵觀察:一台伺服器能通訊,當且僅當它所在的行或列至少有另一台伺服器。
時間複雜度:O(m × n) — 遍歷兩次網格,第一次統計行列伺服器數量,第二次統計可通訊的伺服器
空間複雜度:O(m + n) — 儲存每一行和每一列的伺服器計數
1. Initialize rowCount[m] and colCount[n] to 0 2. First pass: for each cell (i, j) where grid[i][j] == 1, increment rowCount[i] and colCount[j] 3. Second pass: for each cell (i, j) where grid[i][j] == 1, if rowCount[i] > 1 OR colCount[j] > 1, increment result 4. Return result
方法二:Union-Find(並查集) 將同一行或同一列的伺服器合併到同一個集合中,最後統計集合大小 > 1 的伺服器數量。時間複雜度 O(m × n × α(m × n)),空間複雜度 O(m × n)。相比計數法更複雜,但展示了圖論思維。
方法三:BFS/DFS 將每台伺服器視為節點,同行或同列的伺服器之間建立邊,用 BFS/DFS 找連通分量。大小 > 1 的連通分量中的所有伺服器都能通訊。時間空間複雜度較高,不推薦。