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.

click to show follow up.

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;
        }
    }
};