描述 Description

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

[Set Matrix Zeroes]

分析 Analysis

方法1

O(m+n)空间的方法：设置两个bool数组，记录每行和每列是否存在0。

方法2

常数空间，可以复用第一行和第一列作为bool数组使用，记录行列是否有0的状态。（或者也可以扫描到第一个0的行和列作为bool数组使用，但是没必要，第一列和第一行就可以了）。有一点需要注意的是，matrix[0][0]既保存了0行有没有0，也保存了0列有没有0，所以这是不可以的，这样我们就额外设置一个bool类型变量col0来记录列0中是否有0，而列0记录的是每行是否有0。

时间复杂度O(m*n)，空间复杂度O(1)。

代码 Code

方法2

class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
    bool col0 = false;
    int rows = matrix.size(), cols = matrix[0].size();

    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) col0 = true;
        for (int j = 1; j < cols; j++)
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
    }

    for (int i = rows - 1; i >= 0; i--) {
        for (int j = cols - 1; j >= 1; j--)
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        if (col0) matrix[i][0] = 0;
    }
}
};