1582. Special Positions in a Binary Matrix

📘 題目敘述

給你一個 m x n 的二元矩陣 mat，請回傳 mat 中 special position 的數量。

位置 (i, j) 被稱為 special，若 mat[i][j] == 1 且第 i 列與第 j 行的其他所有元素都是 0（列與行皆為 0-indexed）。

條件限制

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] 只會是 0 或 1

🧠 解題思路

special position 的條件其實可以拆成三件事：

• 該格本身是 1
• 所在列的 1 數量剛好是 1
• 所在行的 1 數量也剛好是 1

所以我先掃描一次矩陣，分別統計每一列與每一行有多少個 1，再掃第二次去確認哪些位置同時符合列唯一與行唯一。

所有變數

• m：列數
• n：行數
• row：row[i] 代表第 i 列有幾個 1
• column：column[j] 代表第 j 行有幾個 1
• count：special positions 的數量

🪜 主要流程步驟

1. 先掃一次矩陣，統計每列 / 每行的 1 的數量

看到 mat[i][j] == 1 時就更新：

• row[i]++
• column[j]++

2. 再掃一次，只檢查 row[k] == 1 的列

如果某列不只一個 1，那一列不可能產生 special position，所以可以直接跳過。

3. 在該列找到 1，並檢查它所在的行是否也只有一個 1

對每個位置 (k, l)，若 mat[k][l] == 1 且 column[l] == 1，代表它同時是列唯一與行唯一，count++。

4. 回傳 count

第二次掃描結束後，count 就是答案。

⏱️ 複雜度

• 時間複雜度：O(mn)，因為做了兩次矩陣掃描。
• 空間複雜度：O(m + n)，使用了 row 與 column 兩個計數陣列。

💻 程式碼實作

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

🔗 題目連結

https://leetcode.com/problems/special-positions-in-a-binary-matrix/