LC 73. 矩阵置零

题目描述

这是 LeetCode 上的 73. 矩阵置零 ，难度为 中等。

给定一个 $m \times n$ 的矩阵，如果一个元素为 $0$ ，则将其所在行和列的所有元素都设为 $0$ 。

请使用「原地」算法。

进阶：

• 一个直观的解决方案是使用 $O(m \times n)$ 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 $O(m + n)$ 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

示例 1：

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

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

示例 2：

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

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

提示：

• $m = matrix.length$
• $n = matrix[0].length$
• $1 <= m, n <= 200$
• $-2^{31} <= matrix[i][j] <= 2^{31} - 1$

---

前言

由于 $O(m \times n)$ 和 $O(m+n)$ 空间的解法都十分简单，无非是「同等大小的矩阵」或「与行列数量相等的标识」来记录置零信息。

这里着重讲解利用原矩阵的 $O(1)$ 空间解法。

---

O(1) 空间

1. 使用两个变量（r0 & c0），记录「首行 & 首列」是否该被置零

2.「非首行首列」的位置

• 将置零信息存储到原矩阵
• 根据置零信息，置零「非首行首列」的位置

3. 使用 r0 & c0 ，置零「首行 & 首列」

Java 代码：

class Solution {
    public void setZeroes(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        // 1. 扫描「首行」和「首列」记录「首行」和「首列」是否该被置零
        boolean r0 = false, c0 = false;
        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 0) {
                r0 = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (mat[0][j] == 0) {
                c0 = true;
                break;
            }
        }
        // 2.1 扫描「非首行首列」的位置，如果发现零，将需要置零的信息存储到该行的「最左方」和「最上方」的格子内
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][j] == 0) mat[i][0] = mat[0][j] = 0;
            }
        }
        // 2.2 根据刚刚记录在「最左方」和「最上方」格子内的置零信息，进行「非首行首列」置零
        for (int j = 1; j < n; j++) {
            if (mat[0][j] == 0) {
                for (int i = 1; i < m; i++) mat[i][j] = 0;
            }
        }
        for (int i = 1; i < m; i++) {
            if (mat[i][0] == 0) Arrays.fill(mat[i], 0);
        }
        // 3. 根据最开始记录的「首行」和「首列」信息，进行「首行首列」置零
        if (r0) for (int i = 0; i < m; i++) mat[i][0] = 0;
        if (c0) Arrays.fill(mat[0], 0);
    }
}

C++ 代码：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool r0 = false, c0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                r0 = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                c0 = true;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
            }
        }
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) matrix[i][j] = 0;
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) fill(matrix[i].begin(), matrix[i].end(), 0);
        }
        if (r0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
        if (c0) fill(matrix[0].begin(), matrix[0].end(), 0);
    }
};

Python 代码：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        r0, c0 = False, False
        for i in range(m):
            if matrix[i][0] == 0:
                r0 = True
                break
        for j in range(n):
            if matrix[0][j] == 0:
                c0 = True
                break
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        for j in range(1, n):
            if matrix[0][j] == 0:
                for i in range(1, m):
                    matrix[i][j] = 0
        for i in range(1, m):
            if matrix[i][0] == 0:
                matrix[i] = [0] * n
        if r0:
            for i in range(m):
                matrix[i][0] = 0
        if c0:
            matrix[0] = [0] * n

TypeScript 代码：

/**
 Do not return anything, modify matrix in-place instead.
 */
function setZeroes(matrix: number[][]): void {
    let m = matrix.length, n = matrix[0].length;
    let r0 = false, c0 = false;
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            r0 = true;
            break;
        }
    }
    for (let j = 0; j < n; j++) {
        if (matrix[0][j] === 0) {
            c0 = true;
            break;
        }
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) matrix[i][0] = matrix[0][j] = 0;
        }
    }
    for (let j = 1; j < n; j++) {
        if (matrix[0][j] === 0) {
            for (let i = 1; i < m; i++) matrix[i][j] = 0;
        }
    }
    for (let i = 1; i < m; i++) {
        if (matrix[i][0] === 0) {
            for (let j = 0; j < n; j++) matrix[i][j] = 0;
        }
    }
    if (r0) for (let i = 0; i < m; i++) matrix[i][0] = 0;
    if (c0) for (let i = 0; i < n; i++) matrix[0][i] = 0;
};

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

---

最后

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

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

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

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