1582. 二進位制矩陣中的特殊位置 : 簡單模擬題

題目描述

這是 LeetCode 上的 1582. 二進位制矩陣中的特殊位置 ，難度為 簡單 。

Tag : 「模擬」

給你一個大小為 rows x cols 的矩陣 mat ，其中 mat[i][j] 是 0 或 1 ，請返回 矩陣  mat 中特殊位置的數目 。

特殊位置 定義：如果 mat[i][j] = 1 並且第 i 行和第 j 列中的所有其他元素均為 0 （行和列的下標均 從 0 開始 ），則位置 (i, j) 被稱為特殊位置。

示例 1：

輸入：mat = [[1,0,0],
            [0,0,1],
            [1,0,0]]

輸出：1

解釋：(1,2) 是一個特殊位置，因為 mat[1][2] == 1 且所處的行和列上所有其他元素都是 0

示例 2：

輸入：mat = [[1,0,0],
            [0,1,0],
            [0,0,1]]

輸出：3

解釋：(0,0), (1,1) 和 (2,2) 都是特殊位置

示例 3：

輸入：mat = [[0,0,0,1],
            [1,0,0,0],
            [0,1,1,0],
            [0,0,0,0]]

輸出：2

示例 4：

輸入：mat = [[0,0,0,0,0],
            [1,0,0,0,0],
            [0,1,0,0,0],
            [0,0,1,0,0],
            [0,0,0,1,1]]

輸出：3

提示：

• $rows = mat.length$
• $cols = mat[i].length$
• $1 <= rows, cols <= 100$
• $mat[i][j]$ 是 0 或 1

模擬

根據題意，使用陣列 r 和 c 分別預處理除每行和每列所含 $1$ 的個數，複雜度為 $O(m \times n)$。

隨後分別統計特殊位置的個數：滿足 $mat[i][j] = 1$ 且 $r[i] = c[j] = 1$ 的位置。

Java 程式碼：

class Solution {
    public int numSpecial(int[][] mat) {
        int n = mat.length, m = mat[0].length, ans = 0;
        int[] r = new int[n], c = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) r[i] += mat[i][j];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) c[i] += mat[j][i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) ans++;
            }
        }
        return ans;
    }
}

TypeScript 程式碼：

function numSpecial(mat: number[][]): number {
    let n = mat.length, m = mat[0].length, ans = 0
    const r = new Array<number>(n).fill(0), c = new Array<number>(m).fill(0)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) r[i] += mat[i][j]
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) c[i] += mat[j][i]
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) ans++
        }
    }
    return ans
};

• 時間複雜度：$O(m \times n)$
• 空間複雜度：$O(m + n)$

最後

這是我們「刷穿 LeetCode」系列文章的第 No.1582 篇，系列開始於 2021/01/01，截止於起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的程式碼。如果涉及通解還會相應的程式碼模板。

為了方便各位同學能夠電腦上進行除錯和提交程式碼，我建立了相關的倉庫： https://github.com/SharingSou... 。

在倉庫地址裡，你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:

本文由mdnice多平臺釋出