Problem#
給你一個 $mxn$ 的矩陣(mat)，對於 mat[i][j] 來說，第 i 列第 j 排的數字如果只有它是 1 其餘都是 0 的話則稱作特殊位置。問你屬於特殊位置的數字有幾個？
測資限制#
- $1 \le m, n \le 100$
想法#
naive: 暴力掃過 mat[i][j] 接著找該 i 列 j 排是不是只有它一個 1 而已，$O(n^3)$$
imporve: 可以預先掃一次，存下第 i 列和第 j 排有幾個 1 出現，接著再掃一次便可以用剛剛儲存的快速判斷是否只有自己是 1 其他是 0 。
AC Code#
- 時間複雜度: $\mathcal{O}(n^2)$
- 空間複雜度: $\mathcal{O}(n)$