LeetCode之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.

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?

LeetCode Discuss

“The basic idea is to use the first row and column to store the information.

Then we need to know whether or not to set the first row and column to zeroes.

So, we use two boolean to store that information.”

class Solution {
public:
    void setZeroes(vector > &matrix) {
        int rownum = matrix.size();
		if (rownum == 0) return;
		int colnum = matrix[0].size();
		bool hasZeroFirstRow = false, hasZeroFirstColumn = false;

		for (int i = 0; i < rownum; i++)
			if (matrix[i][0] == 0){
				hasZeroFirstColumn = true;
				break;
			}

		for (int i = 0; i < colnum; i++)
			if (matrix[0][i] == 0){
				hasZeroFirstRow = true;
				break;
			}

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

		for (int i = 1; i < rownum; i++)
			for (int j = 1; j < colnum; j++){
				if (matrix[0][j] == 0 || matrix[i][0]==0)
					matrix[i][j] = 0;
				
			}
		
		if (hasZeroFirstRow) {
			for (int j = 0; j < colnum; ++j) 
				matrix[0][j] = 0;
		}

		if (hasZeroFirstColumn) {
			for (int i = 0; i < rownum; ++i)
				matrix[i][0] = 0;
		}
    }
};