一、问题描述
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
二、解决思路
思路一:使用2个数组分别标记置0行和置0列,最后根据两数组对原二维数组置0即可
思路二:上面使用了2个数组,牺牲了空间,为了节省空间,可是用时间换空间,只需要对原数组不为0的元素做标记,最后再重新遍历一遍二维数组将标记元素置0即可
思路三:可以思路二优化,遍历二维数组,若元素为0,只需要将其所在的第一行和第一列元素置0,然后再将二维数组的第一行和第一列元素为0的列和行置0即可
三、算法实现
思路一实现:
public void setZeroes(int[][] matrix) {
int len1 = matrix.length;
if(len1 == 0) return ;
int len2 = matrix[0].length;
int[] r = new int[len1];
int[] w = new int[len2];
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(matrix[i][j] == 0){
if(r[i] == 0){
//nulArr(matrix, i, len1, false);
r[i] = 1;
}
if(w[j] == 0){
//nulArr(matrix, j, len2, true);
w[j] = 1;
}
}
}
}
for(int i = 0; i < len1; i++){
if(r[i] == 1){
nulArr(matrix, i, len2, false);
}
}
for(int i = 0; i < len2; i++){
if(w[i] == 1){
nulArr(matrix, i, len1, true);
}
}
}
private void nulArr(int[][] matrix, int k, int len, boolean flag){
if(flag){
for(int i = 0; i < len; i++){
matrix[i][k] = 0;
}
} else{
for(int i = 0; i < len; i++){
matrix[k][i] = 0;
}
}
}