这是一道面试题:在一个mxn大小的二维数组中,对于每一个值为0的元素,将该元素所在的整行整列都置0,其余元素保持不变。
我能想到的方法是遍历数组中的每个元素,每次遇到零时,我都用零标记整个行和列。但这是幼稚的,请提出任何改进建议。
最佳答案
如果允许额外的空间。只需维护两个标志数组即可。
一个代表行,另一个代表列。所有默认值设置为 1。
扫描你的原始矩阵,假设你在 x 行和 y 列找到一个 0。只需设置 row[x] = 0;和列[y] = 0;
然后再次扫描你的矩阵
for ( int i = 0; i < height; ++i )
for ( int j = 0; j < width; ++j )
M[i][j] = M[i][j] * row[i] * column[j];
然后你得到你的矩阵 M 改变
关于algorithm - 用零标记所有列和行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18640970/