73. Set Matrix Zeroes

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

Follow up:

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?
 

Example 1:


Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:


Input: matrix = [[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]]
 

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

这题将矩阵中存在零值的位置的所有相同行或者相同列的值都置为零。

这里遍历一次，找出所有零存在的坐标，然后再去置零。

class SetMatrixZeros : public Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> zeroRows, zeroCols;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == 0) {
                    zeroRows.push_back(i);
                    zeroCols.push_back(j);
                }
            }
        }
        for (auto row : zeroRows) {
            for(int i = 0; i < matrix[row].size(); i++) {
                matrix[row][i] = 0;
            }
        }
        for (auto col : zeroCols) {
            for (int i = 0; i < matrix.size(); i++) {
                matrix[i][col] = 0;
            }
        }
    }
};