矩阵置零

LeetCode 73

https://leetcode-cn.com/problems/set-matrix-zeroes/

解题思路：

• 本题很容易想到空间复杂度为 O(mn)的解法，用一个boolean矩阵来标记每一个位置是否为空，最后再进行归0操作，也算是暴力解决了。
• 下面提供一种状态压缩的方式，我们可以用原有的第0列和第0行来做标记，标记 row(1~row) col (1~col)这部分矩阵。至于原矩阵的第0行/列，可以用两个变量来记录是否要置0，在最开始进行判断，然后第0行/列就用来记录小矩阵，最后再处理第0行/列。

public class Solution {

    public void setZeroes(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        boolean isRow0 = false, isCol0 = false;
        // 判断第0列是否存在 0，一旦存在则在后面会将这一列全部归0
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                isCol0 = true;
                break;
            }
        }
        // 同上判断第0行是否存在0
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                isRow0 = true;
                break;
            }
        }
        // 标记好后第0列/行后，将作为判断内部矩阵是否存在0的标志数组
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 根据第0列/行记录的结果将对应行列进行归0操作
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 最后将第0列和行判断归0
        if (isCol0) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
        if (isRow0) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
    }

}