Leetcode 1582 - Special Positions in a Binary Matrix

題目

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#

Copy

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat)
    {
        int n = mat.size(), m = mat[0].size();
        int ans = 0;
 
        vector<int> row(n), col(m);
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(mat[i][j] == 1)
                {
                    row[i]++;
                    col[j]++;
                }
            }
        }
 
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(mat[i][j] != 1)
                    continue;
 
                if(row[i] == 1 && col[j] == 1)
                    ans++;
            }
        }
        return ans;
    }
};

view raw leetcode/1582.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n^2)$
• 空間複雜度: $\mathcal{O}(n)$