LeetCode -Hot100 - 73. 矩阵置零

前言

本专栏主要通过“LeetCode 热题100”，来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~

题目描述

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

思路

最开始我不知道什么是“原地算法”。gpt给的答复是：原地算法（In-place algorithm）是指在执行算法时不需要额外的存储空间，或者只需要常数级别的额外存储空间的算法。换句话说，算法的输入数据被直接修改以产生输出结果，而不需要创建额外的数据结构来存储输出结果或中间结果。
如果只是不用额外的数组来存储二维数组，不难。只要发现一个0然后对当前的数组的行列赋值0就好，但需要注意不要把后面没有开始判断的数字给赋值0了。既然怕前面的赋值操作影响后面的数组，其实完全可以用数组记录下来哪些行和列要归0。然后最后统一来赋值0就好。

Java代码如下：

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //发现0
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;//只需要记录下来这些row 和 col为true
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] == true || col[j] == true) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}