$$\color{Red}{矩阵置0【leetcode73 数组记录】}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

题目介绍

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 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 * n) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

解析

这个题目说的使用 O(m * n) 的空间，肯定就是开一个一样大小的数组，然后进行第一个数组的枚举并把不为 0 的数填到第二个矩阵，一旦有一个位置为 0，就进行对应新数组的那个位置的行和列的元素置 0。相当于时间 O(n ^ 3) ，这么丑陋的算法，讲道理肯定真不会有人这么写吧。

改进也很简单，做过 八皇后的肯定懂 我的八皇后题解 ，直接用两个数组，分别大小为原数组的长和高。记录对应的行和列，一旦出现 0 ，就把对应位置的 行和列的数组置 0，最后直接根据这个数组进行原地的数字转换即可。

但是这道题要求空间 O(1) ，那只能完全在原地进行操作了，线性也不行。其实可以直接使用第一行和第一列，一旦对应行和列出现 0，直接记录在这里，然后最后根据第一行和第一列的记录给数组原地进行更新即可。

但是这么做很尬的一点是，如果是第一行或第一列自身出现了0，就没位置能存了，但是只需要开两个常数的变量存第一行和第一列是否置0即可，满足空间线性。

class Solution {
    public void setZeroes(int[][] matrix) {
        int r0 = 1, c0 = 1;
        int n = matrix.length, m = matrix[0].length;

        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) r0 = 0; // 第 0 行自身出现 0 元素
                    if (j == 0) c0 = 0; // 第 0 列自身出现 0 元素
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        // 根据第 0 行进行原地更新
        for (int i = 1; i < n; i ++)
            if (matrix[i][0] == 0)
                for (int j = 1; j < m; j ++)
                    matrix[i][j] = 0;
        // 根据第 0 列进行原地更新        
        for (int i = 1; i < m; i ++)
            if (matrix[0][i] == 0)
                for (int j = 1; j < n; j ++)
                    matrix[j][i] = 0;
        // 最后更新第 0 行和第 0 列本身
        if (r0 == 0) for (int i = 0; i < m; i ++) matrix[0][i] = 0;
        if (c0 == 0) for (int i = 0; i < n; i ++) matrix[i][0] = 0;
    }
}