73.Set Matrix Zeroes

给定一个矩阵，如果矩阵中存在0元素，则将0元素所在行、所在列，都变为0.

Input:
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output:
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

思路：

一、空间复杂度O(m+n)，其中m,n分别为行、列数，先遍历一遍矩阵，将存在0元素的行、列分别记录下来，用两个数组记录，数组大小分别为矩阵的行数、列数，再对记录下来的行、列都使其为0. 相当于一共遍历2遍矩阵。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        vector<int> rowZero(row, 1), colZero(col, 1);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] != 0) continue;
                rowZero[i] = 0; colZero[j] = 0;
            }
        }
        for (int k = 0; k < row; k++) {
            if (rowZero[k] == 1) continue;
            for (int j = 0; j < col; j++) matrix[k][j] = 0;
        }
        for (int k = 0; k < col; k++) {
            if (colZero[k] == 1) continue;
            for (int i = 0; i < row; i++) matrix[i][k] = 0;
        }
    }
};

二、空间复杂度O(1)，分别利用矩阵的第一行记录矩阵中对应列是否有0，而利用第一列记录矩阵对应行是否有0。因为矩阵第一列的数量等于矩阵的行数，其实跟第一种解法一样，只是不占用额外的空间，读起来有点绕口。牺牲了矩阵第一行第一列的空间，那么，对于矩阵中原本第一行、第一列中存在的0，就要用另外的2个bool变量来记录了。总体来说也是遍历2遍矩阵，但这样就没有额外的引入空间复杂度了。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        bool rowZero = false, colZero = false;
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) colZero = true;
        }
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) rowZero = true;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] != 0) continue;
                matrix[0][j] = 0; matrix[i][0] = 0;
            }
        }
        for (int i = 1; i < row; i++) {
            if (matrix[i][0] != 0) continue;
            for (int k = 1; k < col; k++) matrix[i][k] = 0;
        }
        for (int j = 1; j < col; j++) {
            if (matrix[0][j] != 0) continue;
            for (int k = 1; k < row; k++) matrix[k][j] = 0;
        }
        if (rowZero) {
            for (int j = 0; j < col; j++) matrix[0][j] = 0;
        }
        if (colZero) {
            for (int i = 0; i < row; i++) matrix[i][0] = 0;
        }
    }
};