Dada una matriz am * n, si un elemento es 0, establezca toda su fila y columna en 0.
Hágalo en su lugar.
Análisis
Este problema debe resolverse en el lugar, es decir, no se debe utilizar ninguna otra matriz. Podemos usar la primera columna y la primera fila para rastrear si una fila / columna debe establecerse en 0.
Dado que usamos la primera fila y la primera columna para marcar la fila / columna cero, se cambian los valores originales.
Específicamente, dada, la siguiente matriz
este problema se puede resolver siguiendo 4 pasos:
Paso 1:
La primera fila contiene cero = verdadero;
La primera columna contiene cero = falso;
Paso 2: use la primera fila y columna para marcar cero fila y columna.
Paso 3: configure cada elemento usando marcas en la primera fila y columna.
Paso 4: establezca la primera columna y fila usando las marcas en el paso 1.
Solución Java
public class Solution { public void setZeroes(int[][] matrix) { boolean firstRowZero = false; boolean firstColumnZero = false; //set first row and column zero or not for(int i=0; i<matrix.length; i++){ if(matrix[i][0] == 0){ firstColumnZero = true; break; } } for(int i=0; i<matrix[0].length; i++){ if(matrix[0][i] == 0){ firstRowZero = true; break; } } //mark zeros on first row and column for(int i=1; i<matrix.length; i++){ for(int j=1; j<matrix[0].length; j++){ if(matrix[i][j] == 0){ matrix[i][0] = 0; matrix[0][j] = 0; } } } //use mark to set elements for(int i=1; i<matrix.length; i++){ for(int j=1; j<matrix[0].length; j++){ if(matrix[i][0] == 0 || matrix[0][j] == 0){ matrix[i][j] = 0; } } } //set first column and row if(firstColumnZero){ for(int i=0; i<matrix.length; i++) matrix[i][0] = 0; } if(firstRowZero){ for(int i=0; i<matrix[0].length; i++) matrix[0][i] = 0; } } } |
