【路边社】世界各地老苦逼喜迎圣诞 (转载)# Joke - 肚皮舞运动
K*i
1 楼
一个MxN的int矩阵,如果某个元素为0, 则把该元素所在的行和列都置0
要求O(1)空间,这样可以么?
#define M 5
#define N 4
void SetZeros(int A[M][N])
{
int row0 = 1;
int col0 = 1;
for (int j = 0; j < N; j++)
{
if (A[0][j] == 0)
{
row0 = 0;
break;
}
}
for (int i = 0; i < M; i++)
{
if (A[i][0] == 0)
{
col0 = 0;
break;
}
}
for (int i = 1; i < M; i++)
{
for (int j = 1; j < N; j++)
{
if (A[i][j] == 0)
{
A[0][j] = 0;
A[i][0] = 0;
}
}
}
for (int j = 1; j < N; j++)
{
if (A[0][j] == 0)
{
for (int i = 1; i < M; i++)
A[i][j] = 0;
}
}
for (int i = 1; i < M; i++)
{
if (A[i][0] == 0)
{
for (int j = 1; j < N; j++)
A[i][j] = 0;
}
}
if (row0 == 0)
{
for (int j = 0; j < N; j++)
A[0][j] = 0;
}
if (col0 == 0)
{
for (int i = 0; i < M; i++)
A[i][0] = 0;
}
}
要求O(1)空间,这样可以么?
#define M 5
#define N 4
void SetZeros(int A[M][N])
{
int row0 = 1;
int col0 = 1;
for (int j = 0; j < N; j++)
{
if (A[0][j] == 0)
{
row0 = 0;
break;
}
}
for (int i = 0; i < M; i++)
{
if (A[i][0] == 0)
{
col0 = 0;
break;
}
}
for (int i = 1; i < M; i++)
{
for (int j = 1; j < N; j++)
{
if (A[i][j] == 0)
{
A[0][j] = 0;
A[i][0] = 0;
}
}
}
for (int j = 1; j < N; j++)
{
if (A[0][j] == 0)
{
for (int i = 1; i < M; i++)
A[i][j] = 0;
}
}
for (int i = 1; i < M; i++)
{
if (A[i][0] == 0)
{
for (int j = 1; j < N; j++)
A[i][j] = 0;
}
}
if (row0 == 0)
{
for (int j = 0; j < N; j++)
A[0][j] = 0;
}
if (col0 == 0)
{
for (int i = 0; i < M; i++)
A[i][0] = 0;
}
}