LeetCode第73题矩阵置零

继续打卡算法题，今天学习的是LeetCode第73题矩阵置零，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

这个题目最直观的做法是使用一个二维数组，将每行/每列是否有0记录下来。然后再遍历一次矩阵进行置0操作。 这样空间复杂度是O(mn).

有没有其他更优的方法呢？

我们可以使用矩阵数组的第一行，第一列来存储某行某列是否有0标记，然后使用两个遍历来存储第一行，第一列的是否有0标记。

这样空间复杂度变成了O(1)。

本题解题技巧

1、使用原矩阵第一行，第一列记录某行，某列是否存在0的标记，减少了额外空间存储

编码解决

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flagRow0 = true;
            }
        }
        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 i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flagCol0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

总结

1、二维数组遍历的题目，今天又学到了一个技巧，第一行第一列存储标记在本题应用上是非常巧妙的。