## Set Matrix Zeroes

Given a

mxnmatrix, 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?

见注释

class Solution { public: void setZeroes(vector<vector<int> > &matrix) { //o(mn) in time, o(mn) in space solution is trivial. Just allocate another m*n matrix as our destnation matrix //All the stories happen in it. And we copy the destination matrx to original matrix. //o(mn) in time, o(m+n) in space solution is tricky. Allocate two array "row" and "column" to record the rows and columns that should be filled with 0. //And do it in original matrix. //o(mn) in time, o(1) in space is what this problem what's. //First, we find the first 0 cell in the matrix. (If no 0 cell is found, just return the original matrix, all works are done.) //Second, since we record the row number and column number of the first 0 cell. We know this row and column should be filled with 0 //in the result matrix. With the help of variable "row" and "column", we can use this row array and column array to serve as //the "row" array and "column" array in o(mn) in time, o(m+n) in space algorithm. //To be more specific, if[3][2] is the first cell we found that is 0. we use row [3][] to record which column should be filled with 0 //and column [][2] to record which row should be filled with 0. if(matrix.empty()){ return ; } size_t height = matrix.size(); size_t width = matrix.front().size(); //find the first 0 cell int row = -1; int column = -1; for(size_t i = 0; i < height; i++){ for(size_t j = 0; j < width; j++){ if(matrix[i][j] == 0){ row = i; column = j; break; } } if(row != -1){ break; } } //no 0 cells found if(row == -1){ return ; } //mark all 0 cells for(size_t i = 0; i < height; i++){ for(size_t j = 0; j < width; j++){ if(matrix[i][j] == 0){ matrix[row][j] = 0; matrix[i][column] = 0; } } } //fill corresponding cells with 0 for(size_t i = 0; i < height; i++){ if(i == row) continue; if(matrix[i][column] == 0){ for(size_t j = 0; j < width; j++){ matrix[i][j] = 0; } } } for(size_t j = 0; j < width; j++){ if(j == column) continue; if(matrix[row][j] == 0){ for(size_t i = 0; i < height; i++){ matrix[i][j] = 0; } } } //fill row,column for(size_t i = 0; i < height; i++){ matrix[i][column] = 0; } for(size_t j = 0; j < width; j++){ matrix[row][j] = 0; } } };