73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
方法
对于此题,理解题意很重要,当矩阵中的值置为0后,它便不能再进行比较。充分理解题意后开始解题,使用第0行和第0列存储哪行哪列有0.将置0分为两部分,一部分为从matrix[1][1]
开始到matrix[m][n]
,若matrix[i][j] = 0
,则令matrix[i][0] = 0,matrix[0][j] = 0
,即将其拆分,分别放在其第i行0列和第0行j列的位置,之后遍历置0。第二部分遍历第0行和第0列,若其中有一个为0,相对应的第0行或第0列置0。使用该方法空间复杂度为O(1),即只需存储变量row和col。
public class Solution {
public void setZeroes(int[][] matrix) {
//行
int m = matrix.length;
//列
int n = matrix[0].length;
//用第一行和第一列来存储哪行哪列有0
boolean row = false;
boolean col = false;
for(int i = 0; i < m; i++){
if(matrix[i][0] == 0){
row = true;
break;
}
}
for(int j = 0; j < n; j++){
if(matrix[0][j] == 0){
col = true;
break;
}
}
//从第一行和第一列开始,若某行某列为0,标记
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;
}
}
}
//从第一行开始遍历,若第i行第0列为0,则第i行都为0
for(int i = 1; i < m; i++){
if(matrix[i][0] == 0){
for(int j = 1; j < n; j++){
matrix[i][j] = 0;
}
}
}
//从第1行第j列开始遍历,若第0行第j列为0,则第i行第j列为0
for(int j = 1; j < n; j++){
if(matrix[0][j] == 0){
for(int i = 1; i < m; i++ ){
matrix[i][j] = 0;
}
}
}
//若第0-i行有0,则第i行第0列为0
if(row == true){
for(int i = 0; i < m; i++){
matrix[i][0] = 0;
}
}
//若第0-i列有0,则第0行第j列为0
if(col == true){
for(int j = 0; j < n; j++){
matrix[0][j] = 0;
}
}
}
}