Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
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?
思路
参考http://www.voidcn.com/article/p-nodlrltb-bdw.html
方案一： 用2个extra array来记录该行该列是否需要设置为0
使用两个数组来标记某一行或是某一列是否存在 0。这是一种 O(m + n) 空间复杂度的实现方式。
共3次循环
- 第一次循环，设置这2个数组的flag
- 第二次循环，根据rowFlgArray设置矩阵的行为0
- 第三次循环，根据colFlgArray设置矩阵的列为0
class Solution {
public void setZeroes(int[][] matrix) {
/* solution 1**********************
//SOLUTION1. O(m + n)的方法，有2个数组，分别记录该行和该列是否需要设置为0
if (matrix == null || matrix[0].length == 0 || matrix.length == 0) {
return;
}
int row = matrix.length;
int col = matrix[0].length;
int[] rowFlg = new int[col];
int[] colFlg = new int[row];
//1. 设置flg
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
colFlg[i] = 1;
rowFlg[j] = 1;
}
}
}
//3. 根据flg设置row zeros
for (int i = 0; i < row; i++) {
if (colFlg[i] == 1) {
for (int j = 0; j < col; j++) {
matrix[i][j] = 0;
}
}
}
//4. 根据flg设置col zeros
for (int i = 0; i < col; i++) {
if (rowFlg[i] == 1)
for (int j = 0; j < row; j++) {
matrix[j][i] = 0;
}
}
}
方案二：用第一行 第一列来存 该行该列是否需要被设置为0. （不需要extra space）
一共2次遍历矩阵，+ 2次设置第一行/第一列为0（Option）
- 第一次遍历找出标记，设置第一列和第一行。
- 第二次遍历使用标记标注矩阵，第二遍标记的时候不能把标记列（行）本身也遍历一遍，所以要排除标记行和列，从（1，1）开始循环起走，如果碰到第一行和第一列的标志位为0，那么将该元素设置为0。
-
修正第一列和第一行的其他元素：很简单，那么设置两个额外的bool变量告诉第一行和第一列的其他元素是否要变为0.在第一遍遍历的时候如果Matrix[i,j]==0时i和j为0，那么对应的标记就要为true
流程就是第一遍遍历全部，找出标记；第二遍遍历除标记列（行）意外的元素，将必要的元素置为0.第三次遍历标记列（行），根据两个标记考虑是否将其所有元素置为0.
/* solution 2*********************************************************/
//用第一行 第一列来存 该行该列是否需要被设置为0.
//一共两次循环，第一次循环，设置第一列和第一行
//第二次循环，不要循环第一行和第一列，从（1，1）开始循环起走，如果碰到第一行和第一列的标志位为0，那么将该元素设置为0
//第一列和第一行如何表示需要全部设置为0呢？ 在第一次扫描时，用2个boolean flag来标识
if (matrix == null || matrix[0].length == 0 || matrix.length == 0) {
return;
}
int row = matrix.length;
int col = matrix[0].length;
boolean fstRowFlg = false;
boolean fstColFlg = false;
//1. 第一次循环
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
if (i == 0) fstRowFlg = true;
if (j == 0) fstColFlg = true;
}
}
}
//2. 第二次循环，设置去掉第一行第一列后的数组为0
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
//3. set first row into zeros
if (fstRowFlg) {
for (int i = 0; i < col; i++) {
matrix[0][i] = 0;
}
}
//4. set first col into zeros
if (fstColFlg) {
for (int i = 0; i < row; i++) {
matrix[i][0] = 0;
}
}
}
