leetcode Set Matrix Zeroes矩阵设置零

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.

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

void setZeroes(vector
  
    > &matrix) {
		int row = matrix.size();
		if (row < 1) return;
		int col = matrix[0].size();
		vector
   
     colRecorder(col); vector
    
      rowRecorder(row); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (matrix[i][j] == 0) { rowRecorder[i] = true; colRecorder[j] = true; } } } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (rowRecorder[i]) matrix[i][j] = 0; else if (colRecorder[j]) matrix[i][j] = 0; } } }
    
   
  

利用常数空间也可以：

就需要巧妙地利用原来矩阵的空间，这里利用第一行和第一列保存额外信息：

1 先判断号第一行和第一列是否需要全部置零

2 有任何一个该行或者该列的元素为零那么这个第一行或者第一列的元素必然是零，就保存这个零，最后用来判断整个矩阵的这一行或者这一列是否需要置零。

3 最后再根据前面判断，决定是否把这个第一行和第一列置零。

void setZeroes2(vector
  
    > &matrix) 
	{
		int row = matrix.size();
		if (row < 1) return;
		int col = matrix[0].size();
		bool firstRowhasZero = false;
		bool firstColhasZero = false;

		for (int i = 0; i < row && !firstColhasZero; i++)
			if (matrix[i][0] == 0) firstColhasZero = true;	

		for (int i = 0; i < col && !firstRowhasZero; i++)
			if (matrix[0][i] == 0) firstRowhasZero = true;

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

		//注意：这里从1开始
		for (int i = 1; i < row; i++)
		{
			for (int j = 1; j < col; j++)
			{
				if (matrix[i][0] == 0) matrix[i][j] = 0;
				else if(matrix[0][j] == 0) matrix[i][j] = 0;
			}
		}

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

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

class Solution {
public:
	void setZeroes(vector
  
    > &matrix)
	{
		int row = matrix.size();
		if (row < 1) return;
		int col = matrix[0].size();
		bool firstRowhasZero = false;
		bool firstColhasZero = false;

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

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

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

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

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

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