设置矩阵零

Question

给定一个m x n整数矩阵矩阵，如果一个元素为0，则将其整个行和列设置为0。我尝试采取的方法，我们设置第1行和第1列作为参考行和列。我在运行代码时遇到以下运行时错误:" error: AddressSanitizer: heap-buffer-overflow on address....">

class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int x=1, y=1, col=1,row=1;
int m=matrix.size();
int n=matrix[0].size();
//for 1st row i.e considered as reference row for inner matrix
for(int i=0;i<m;i++){
if(matrix[i][0]==0)
x=0;
}
// for 1st column i.e considered as reference column for inner matrix;
for(int a=0;a<n;a++){
if(matrix[0][a]==0)
y=0;
}
//loop for the inner matrix
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][j]==0){
matrix[0][j]=0;
matrix[i][0]=0;
}
}
}
//for iterating over 1st row of the matrix to check for zeroes.
for(int i=1;i<m;i++){
if(matrix[0][i]==0){
while(i<n){
matrix[i][col]=0;
col++;
};
break;
}
}
//for iterating over 1 column of the matrix to check for zeroes
for(int j=1;j<n;j++){
if(matrix[j][0]==0){
while(j<m){
matrix[row][j]=0;
row++;
};
break;
}
}
if(x==0){
for(int i=0;i<m;i++)
matrix[0][i]=0;
}
if(y==0){
for(int j=0;j<n;j++)
matrix[j][0]=0;
}
}
};

Answer 1

不声明col和row，而是使用嵌套循环来遍历第一行和第一列。除此之外，代码中还有一些错误。最终代码如下:

class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int x=1, y=1;
int m=matrix.size();
int n=matrix[0].size();
//for 1st row i.e considered as pointer row for inner matrix
for(int j=0;j<n;j++){
if(matrix[0][j]==0)
x=0;
}
// for 1st column i.e considered as pointer column for inner matrix;
for(int i=0;i<m;i++){
if(matrix[i][0]==0)
y=0;
}
//loop for the inner matrix
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][j]==0){
matrix[i][0]=0;
matrix[0][j]=0;
}
}
}
//for iterating over 1st row of the matrix to check for zeroes.
for(int i=1;i<m;i++){
if(matrix[i][0]==0){
for(int j=1;j<n;j++)
matrix[i][j]=0;
}
}
//for iterating over 1 column of the matrix to check for zeroes
for(int j=1;j<n;j++){
if(matrix[0][j]==0){
for(int i=1;i<m;i++)
matrix[i][j]=0;
}
}
if(x==0){
for(int j=0;j<n;j++)
matrix[0][j]=0;
}
if(y==0){
for(int i=0;i<m;i++)
matrix[i][0]=0;
}
}
};

Answer 2

让我们检查发布代码中的最后一个循环

void setZeroes(vector<vector<int>>& matrix) {
// ...     ^^^^^^^^^^^^^^^^^^^            I assume a row-major representation 
int col=1,row=1;

int m = matrix.size();
//  ^^^^^^^^^^^^^^^^^        Let's call it the number of rows.
int n = matrix[0].size();
//  ^^^^^^^^^^^^^^^^^^^^     That's the number of columns. Let's "hope" that
//                           the vector isn't empty and that all the rows
//                           have the same number of columns.

// ...
for(int i=1;i<m;i++){
//          ^^^              Note the limit: 'm', which is the number of rows.
if(matrix[0][i]==0){
//          ^^^          We are traversing the first row, but if 'n' < 'm'
//                       that access has undefined behavior.

//  Now, I guess you'd want to zero an entire column, but it should
//  be the one where the zero in the first row is.
while( i < n ){
// ^^^^^         So, what does 'i' represents now?
matrix[i][col]=0;
//     ^^^^^^    are you trying to access a row or a column?
col++;
//               'i' isn't modified, so this loop is either
//               infinite or never executed.
};
break; //            Why? Why is it here?          
}
}
// ...
}

该算法(使用O(1)个额外空间解决问题的算法)的可能实现如下:

#include <algorithm>
#include <vector>
void setZeroes(std::vector<std::vector<int>>& matrix)
{
if ( matrix.empty() ) return;
// Use the first row and column to memorize which column or row to set to zero.
// matrix[0][0] is used for the first row, so we need an extra variable for
// the first column.
bool first_column_has_zero{};
for ( size_t i{}; i < matrix.size(); ++i )
{
if ( matrix[i][0] == 0 )
first_column_has_zero = true;
for ( size_t j{1}; j < matrix[i].size(); ++j )
{
if ( matrix[i][j] == 0 )
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// Now modify all the rows and columns other than the first ones.
for ( size_t i{1}; i < matrix.size(); ++i )
{
if ( matrix[i][0] == 0 )
{
std::fill(matrix[i].begin() + 1, matrix[i].end(), 0);
}
else
{
for ( size_t j{1}; j < matrix[i].size(); ++j )
{
if ( matrix[0][j] == 0 )
matrix[i][j] = 0;
}
}
}
// At last, deal with the first row and column.
if ( matrix[0][0] == 0 )
std::fill(matrix[0].begin(), matrix[0].end(), 0);
if ( first_column_has_zero )
for ( size_t i{}; i < matrix.size(); ++i )
{
matrix[i][0] = 0;
}
}

我实际上更喜欢空间中的O(n + m)，因为它更直接，但您的里程可能会有所不同:

#include <algorithm>
#include <vector>
void setZeroes(std::vector<std::vector<int>>& matrix)
{
if ( matrix.empty() ) return;
std::vector<bool> rows(matrix.size());
std::vector<bool> cols(matrix[0].size());
for ( size_t i{}; i < matrix.size(); ++i )
{
// assert(matrix[i].size() == cols.size());
for ( size_t j{}; j < cols.size(); ++j )
{
if ( matrix[i][j] == 0 )
{
rows[i] = true;
cols[j] = true;
}
}
}
for ( size_t i{}; i < matrix.size(); ++i )
{
if ( rows[i] )
{
std::fill(matrix[i].begin(), matrix[i].end(), 0);
}
else
{
std::transform( matrix[i].begin(), matrix[i].end()
, cols.cbegin()
, matrix[i].begin()
, [](auto a, auto b){ return b ? 0 : a; });
}
}
}