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

語言: CN / TW / HK

題目描述

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

Tag : 「模擬」

給你一個大小為 rows x cols 的矩陣 mat ,其中 mat[i][j]01 ,請返回 矩陣  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]$ 是 01

模擬

根據題意,使用數組 rc 分別預處理除每行和每列所含 $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多平台發佈