73. Set Matrix Zeroes

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

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

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]
]

Follow up:

• A straight forward solution using O(m**n) 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?

思路

如果没有空间复杂度的要求，很简单，三种空间复杂度解法如下：

O(mn)：直接新建一个和matrix等大小的矩阵，然后一行一行的扫，只要有0，就将新建的矩阵的对应行全赋0。最后将更新完的矩阵赋给matrix即可。

O(m+n)：用一个长度为rows的一维数组记录各行中是否有0，用一个长度为cols的一维数组记录各列中是否有0，最后直接更新matrix数组。

O(1)：不能新建数组，所以这里考虑就用原数组的第一行第一列来记录各行各列是否有0。最后先根据记录来更新其他元素，最后更新第一行和第一列。

C++11

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

        for (decltype(rows) i = 0; i < rows; ++i)
            if (matrix[i][0] == 0) col_0 = true;
        for (decltype(cols) j = 0; j < cols; ++j)
            if (matrix[0][j] == 0) row_0 = true;

        for (decltype(rows) i = 0; i < rows; ++i) 
            for (decltype(cols) j = 0; j < cols; ++j) 
                if (matrix[i][j] == 0) matrix[0][j] = matrix[i][0] = 0;

        for (decltype(rows) i = 1; i < rows; ++i)
            for (decltype(cols) j = 1; j < cols; ++j)
                if (matrix[0][j] == 0 || matrix[i][0] == 0) matrix[i][j] = 0;

        if (row_0)
            for (decltype(cols) j = 0; j < cols; ++j) matrix[0][j] = 0;
        if (col_0)
            for (decltype(rows) i = 0; i < rows; ++i) matrix[i][0] = 0;
    }
};