73.Set Matrix Zeroes¶

73.Set Matrix Zeroes¶

Tags: Medium Array

Links: https://leetcode.com/problems/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?

Answer:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<int> row; 
        set<int> col;

        for (int i = 0; i < matrix.size(); ++i){
            for (int j = 0; j < matrix[i].size(); ++j){
                if (matrix[i][j] == 0){
                    row.insert(i);
                    col.insert(j);
                } 
            }
        }

        for (auto iter_row = row.begin(); iter_row != row.end(); ++iter_row){
            for (int j = 0; j < matrix[0].size(); ++j)
                matrix[*iter_row][j] = 0;
        }

        for (auto iter_col = col.begin(); iter_col != col.end(); ++iter_col){
            for (int i = 0; i < matrix.size(); ++i)
                matrix[i][*iter_col] = 0;
        }
    }
};

$O(m+n)$ 的方法可以做一定的改进，因为设置为0关心的只有行号和列号，那么采取一个set的数据结构来存储行号和列号，保证了最后的结果不重不漏，依次删除即可，但是由于题目建议采取 $O(1)$ 的存储空间，所以改进版本是：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        bool row = false, col = false;

        for (int i = 0; i < matrix.size(); ++i){
            if (matrix[i][0] == 0)
                col = true;
        }

        for (int j = 0; j < matrix[0].size(); ++j){
            if (matrix[0][j] == 0)
                row = true;
        }

        for (int i = 1; i < matrix.size(); ++i){
            for (int j = 1; j < matrix[i].size(); ++j){
                if (matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < matrix.size(); ++i) {
            for (int j = 1; j < matrix[0].size(); ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (row){
            for (int j = 0; j < matrix[0].size(); ++j)
                matrix[0][j] = 0;
        }

        if (col){
            for (int i = 0; i < matrix.size(); ++i)
                matrix[i][0] = 0;
        }  
    }
};

既然不允许额外开辟大的存储空间，那么不妨充分利用好矩阵的第一行和第一列。这里，矩阵的第一行和第一列充当了上面所说的set的作用，用来记录这一行或列是否有0出现，然后矩阵去掉第一行和第一列遍历，如果子矩阵里有0，则把第一行和第一列里的对应行和对应列设置为0 。那么最后读取第一行和第一列的数，遇到0就把相应的行和列上的数全部置为0即可。

但是会存在一个问题，如果第一行和第一列有0怎么办，比如第一行第一个数就是0，那么第一行的所有数全都是0了，然后整个矩阵都会变成0。所以上述方法需要改进。由于第一行和第一列是否需要全部置为0只需要判断这一行是否存在0，那么只需要两个bool值来记录即可。

思路整理：

首先遍历第一行和第一列，检查是否有0，如果有0，则bool类型的row col设置为0.
矩阵去掉第一行和第一列，如果存在0，则第一行对应的列，第一列对应的行设置为0.
检查第一行和第一列，遇到0就把去掉第一行和第一列的子矩阵对应的行和列上的数置为0.
检测row col，如果为true，则第一行或第一列所有数全都置为0 。