LC 面试题 01.08. 零矩阵

题目描述

这是 LeetCode 上的 面试题 01.08. 零矩阵 ，难度为 中等。

编写一种算法，若 $M \times N$ 矩阵中某个元素为 $0$，则将其所在的行与列清零。

示例 1：

输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2：

输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]

输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

---

模拟

根据题意进行模拟。

Java 代码：

class Solution {
    public void setZeroes(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        boolean[] rows = new boolean[n], cols = new boolean[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) rows[i] = cols[j] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rows[i] || cols[j]) mat[i][j] = 0;
            }
        }
    }
}

TypeScript 代码：

function setZeroes(mat: number[][]): void {
    const n = mat.length, m = mat[0].length
    const rows = new Array<boolean>(n).fill(false), cols = new Array<boolean>(m).fill(false)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (mat[i][j] == 0) rows[i] = cols[j] = true
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (rows[i] || cols[j]) mat[i][j] = 0
        }
    }
};

Python 代码：

class Solution:
    def setZeroes(self, mat: List[List[int]]) -> None:
        n, m = len(mat), len(mat[0])
        rows, cols = [False] * n, [False] * m
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 0:
                    rows[i] = cols[j] = True
        for i in range(n):
            for j in range(m):
                mat[i][j] = 0 if rows[i] or cols[j] else mat[i][j]

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(n + m)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.面试题 01.08 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。