前往
大廳
主題

LeetCode - 1582. Special Positions in a Binary Matrix 解題心得

Not In My Back Yard | 2023-01-18 12:00:01 | 巴幣 0 | 人氣 164

題目連結:


題目意譯:
給定一個 m × n 的二元矩陣 mat,回傳 mat 中特殊位置的數量。

一個位置 (i, j) 被稱為是特殊的,代表 mat[i][j] == 1 且同在第 i 列或第 j 行的其他元素皆為 0(列數以及行數索引值從 0 開始)。

限制:
m == mat.length
n == mat[i].length
1 ≦ m, n ≦ 100
mat[i][j] 只會是 0 或是 1。



範例測資:
範例 1:
輸入: mat = [[1,0,0],[0,0,1],[1,0,0]]
輸出: 1
解釋: (1, 2) 為一個特殊位置,因為 mat[1][2] == 1 且且同在第 1 列或第 2 行的其他元素皆為 0。

範例 2:
輸入: mat = [[1,0,0],[0,1,0],[0,0,1]]
輸出: 3
解釋: (0, 0)、 (1, 1) 和 (2, 2) 皆為特殊位置。


解題思維:
因為矩陣 mat 中的數字要嘛是 0 、要嘛就是 1。因此把同一列的數字各自加總、同一行的數字各自加總,然後存在兩個陣列 rowSums 和 columnSums 之中。例如 rowSums[5] 代表第 5 列的總和、columns[0] 代表第 0 行的總和。

接著掃過一次 mat 中的每個元素 mat[i][j]。當 mat[i][j] 是 1 且 rowSums[i] + columnSums[j] 為 2 時,代表 mat[i][j] 為該列該行唯一一個 1,因此其為特殊位置。

因此掃兩次 mat(一次求總和、一次檢查)便可以求得特殊位置的數量。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作