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 ，置零「首行 & 首列」

代码：

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);
    }
}

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

---

最后

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

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

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

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