给定一个矩阵，把零值所在的行和列都置为零。例如：
1 2 3
1 3
1 1 1
操作之后变为
1 3
0 0 0
1 1
方法1：
赋值另存一个m*n的矩阵，在原矩阵为零的值相应置新的矩阵行和列为零。额外空间为O(m*n).
方法2：
两个数组，bool[m] 和 bool[n] 分别存某行有零，后者某列有零。之后根据数组值将原矩阵相应位置置零。额外空间O(m + n)。
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
int len1 = matrix.size();
if (len1 == ) return ;
int len2 = matrix[].size();
if (len2 == ) return ;
vector<bool > row(len1), col(len2);
for (int i = ; i < len1; i++)
for (int j = ; j < len2; j++)
{
if (matrix[i][j] == )
{
row[i] = true; col[j] = true;
}
}
for (int i = ; i < len1; i++)
for (int j = ; j < len2; j++)
{
if (row[i] == true)
matrix[i][j] = ;
else if (col[j] == true)
matrix[i][j] = ;
}
return ;
}
};
方法3：（常数额外空间）
1. 找到一个零的位置，把这行这列当做方法2中的两个数组存值。
2. 根据1的位置的所在行和列的值是否有零将矩阵相应位置置零。
3. 再把1中零所在位置的行和列置零。
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
int len1 = matrix.size();
if (len1 == ) return ;
int len2 = matrix[].size();
if (len2 == ) return ;
int row = -, col = -;
for (int i = ; i < len1; i++)
for (int j = ; j < len2; j++)
{
if (matrix[i][j] == )
{
row = i; col = j;
}
}
if (row == -) return;
for (int i = ; i < len1; i++)
for (int j = ; j < len2; j++)
{
if (matrix[i][j] == && i != row && j != col)
{
matrix[i][col] = ;
matrix[row][j] = ;
}
}
for (int i = ; i < len1; i++)
for (int j = ; j < len2; j++)
{
if (i != row && j != col)
{
if (matrix[i][col] == )
matrix[i][j] = ;
else if (matrix[row][j] == )
matrix[i][j] = ;
}
}
int index = -;
while(++index < len1) matrix[index][col] = ;
index = -;
while(++index < len2) matrix[row][index] = ;
return ;
}
};
2015/03/25:
Python:
用第一行和第一列记录这一行和这一列中是否有零，当然，一开始要先用row和col记录第一行和第一列是否有零，最后再根据这个判断是否将第一行第一列置零
class Solution:
# @param matrix, a list of lists of integers
# @return nothing (void), do not return anything, MODIFY matrix IN PLACE.
def setZeroes(self, matrix):
if len(matrix) == 0:
return ;
row, col = 1, 1
for i in range(0, len(matrix)):
if matrix[i][0] == 0:
col = 0
for j in range(0, len(matrix[0])):
if matrix[0][j] == 0:
row = 0 for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0 if col == 0:
for i in range(0, len(matrix)):
matrix[i][0] = 0
if row == 0:
for j in range(0, len(matrix[0])):
matrix[0][j] = 0